- 1项目经理--要具备的能力_项目经理需要具备哪些能力
- 2[FPGA]FPGA设计EtherCAT主站的方法和常见问题_ethercat fpga 延迟
- 3BARD COMMUNICATIONS PC104-DPIO DRL-DPM-BKF 过程监控冗余处理器
- 4Node.js 框架有哪些框架？(具体分析）_nodejs框架
- 5SPI接口的FPGA实现（一）——SPI接口的相关基础知识_fpga spi接口
- 6小程序获取用户手机号_小程序获取手机号
- 7Mac idea 添加git 拉取代码_mac idea git
- 8数据结构：循环队列（C语言实现）_数据结构循环队列c语言实现
- 9亚马逊开放个人卖家验证入口？亚马逊卖家验证到底怎么搞？_卖家身份验证 您正在请求批准注册。选择个人还是公司
- 10Spring Boot 学习记录笔记【 五 】之前端Vue_ant design vue官方文档
剑指offer刷题详细分析：part10：46题——50题_他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱
赞
踩
-
剑指offer所有题目详解，可访问我的github项目：KongJetLin-offer
-
目录
- Number46：孩子们的游戏（圆圈中最后剩下的数）
- Number47：求解 1+2+3+…+n
- Number48：不用加减乘除做加法
- Number49：把字符串转换成整数
- Number50：数组中重复的数字
题目46 孩子们的游戏（圆圈中最后剩下的数）
题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数…这样下去…直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)。
如果没有小朋友，请返回-1。
分析：
这里n代表的是孩子的人数，而m代表的是报数的人次（每次从0报到m-1，一共报了m人次，我们让第m人出列，即每次遍历m次，就让最后一个人出列）。有2个方法：
1）方法1：用环形链表模拟圆圈。
创建一个总共有 n 个结点的环形链表，然后每次在这个链表中删除第 m 个结点。这种方法的时间复杂度是 O(nm)，不推荐使用这种方法。
代码如下：
private class ListNode { int val; ListNode next; public ListNode(int val) { this.val = val; } } //方法 public int LastRemaining_Solution1(int n, int m) { if(n==0 || m==0) return -1; ListNode cur = new ListNode(0);//当前结点 ListNode head = cur;//创建一个指针指向当前结点，也就是环形链表头结点 //下面通过循环确定环形链表的所有结点 for (int i = 1; i < n; i++) { cur.next = new ListNode(i); cur = cur.next; } //出循环的时候，cur指向第n个结点，我们使得第n个结点的next指向head，就形成环形链表 cur.next = head; //下面通过2层循环，逐步去除链表中每次循环的 m 个结点（因为每次报数人数为m，我们使得报m-1的人，也就是第m人出列） //当 cur.next = cur的时候，说明链表其他结点删除完（圆圈中只有一个小孩，这个结点的值就是小孩的编号），否则继续循环 /** 我们使得cur指向每次m循环开始结点的前一个结点，这样方便将第m个结点删除。（m循环是指每次报数从0到m） 比如我们第一次m循环，此时开始结点为head（0），cur.next = head，cur指向此次m循环开始结点的前一个结点， 我们使得cur走过m-1步，它就指向这次报数的第m-1个结点，我们就可以将这次报数的第m个结点删除。 下一次报数（m循环），开始结点为上一层循环的m+1个结点，此时cur指向m-1个结点，m结点被删除，cur刚刚好指向 这次m循环开始结点的上一个结点，继续进行删除。 */ while(cur.next != cur) { //cur在m循环开始结点的前一个结点，每次循环使得其走过m步，到达m-1结点处 for (int i = 1; i < m ; i++) { cur = cur.next; } cur.next = cur.next.next;//将这次m循环的第m个结点删除 } //出循环，最后剩下的结点就是最后的孩子 return cur.val; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
2）方法2：本题就是著名的约瑟夫（Josephuse）环的问题。我们可以使用递推公式来解答。
如上分析，我们知道，第一个出列的人编号为 (m-1)%m，剩下的n-1个人组成了一个新的约瑟夫环（以编号为k=m%n的人开始）：k k+1 k+2 … n-2, n-1, 0, 1, 2, … k-2（k-1位置的数被删除），并且从编号为k的问开始报0。
我们将下标进行转换，以计算 (n-1) 人的约瑟夫环的结果：
k ——> 0
k+1 ——> 1
....
n-1 ——> ...
0 ——> ...
...
k-3 ——> n-3
k-2 ——> n-2
（由于k-1位置的数被删除，那么k-2 ——> n-2，即第n-1个数原来的下标为k-2）
注意，此处元素只有n-1个，将右边元素下标转换为坐标的元素下标：(右边下标+k)%n=左边下标
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
如果我们可以求得 (n-1) 个人的约瑟夫环的解的下标，那么我们就可以通过反坐标的变换，求得 n 个人的约瑟夫环解的下标。
对此，设 n 个人的约瑟夫环解的下标为：f(n,m)， (n-1) 个人的约瑟夫环的解的下标为：f(n-1,m)，由上面的坐标转换，我们先求得 n 个人的约瑟夫环解对应的k值（因为k=m&n，对长度不同的约瑟夫环，k的取值不同）：k=m%n，随后，将 (n-1) 个人的约瑟夫环的解的下标转换为 n 个人的约瑟夫环解的下标：f(n,m) = (f(n-1,m)+k)%(n-1) = (f(n-1,m)+m%n)%n = (f(n-1,m)+m)%n。（对不同的约瑟夫环，m的值是不变的，n的值是变化的）
- 注：(a+b%c)%c=(a+b)%c，下面给出证明。
由此，我们令 f(i,m) 表示i个人玩游戏报m退出最后胜利者的编号，令 f(i-1,m) 表示 (i-1) 个人玩游戏报m退出最后胜利者的编号，根据上面的分析，有：f(i,m) = ( f(i-1,m) + m)%i，据此，我们可以得到递推公式：
f(1，m) = 0; ——> 如果只有一个人在报数，最后结果一定是这个人的下标：0
f(i,m) = ( f(i-1,m) + m)%i
- 1
- 2
根据递推公式，我们可以得到如下代码：
public int LastRemaining_Solution(int n, int m) { if(n==0 || m==0) return -1; /** 递推公式： f(i,m) = ( f(i-1,m) + m)%i */ int f_1 = 0;//只有一个人的约瑟夫环的解 f(1,m) int temp = f_1; //下面我们用循环解，其实也可以用递归解 for (int i = 2; i <=n ; i++) { temp = (temp+m)%i; } //出循环的时候，找到约瑟夫环长度为n的时候的解 return temp; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
(a+b%c)%c=(a+b)%c，下面给出证明
假设：
a = x*c + z1
b = y*c + z2
其中x，y，z1，z2∈Z,且|z1|<|c|,|z2|<|c|
那么
(a+b%c)%c = (x*c + z1 + (y*c + z2)%c) = (x*c +z1 + z2)%c = (z1 + z2)%c
而(a+b)%c = (x*c + z1 + y*c + z2)%c = (z1+z2)%c
两式相等，得证 (a+b%c)%c=(a+b)%c
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
题目47 求解 1+2+3+…+n
题目描述：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
方法1：递归
由于只能使用加减，不能使用乘除、判断、循环等语句，我们考虑使用递归。
//递归
public static int Sum_Solution(int n) {
int sum = 0;
//最小规模的问题
if(n == 0)
return 0;
//解决较小规模的问题：求解1+2+..+n-1
//将较小问题的解整合成为较大问题的解：n+(1+2+..+n-1)
sum = n + Sum_Solution(n-1);
return sum;
//运行时间：18ms,占用内存：9372k
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
方法2：可以使用公式方法 1 + 2 + 3 + … + n = (n + 1)n / 2，加上Math类的pow方法
代码如下
//公式法
public static int Sum_Solution2(int n)
{
int result = (int)Math.pow(n,2)+n;
return result/2;
//运行时间：12ms,占用内存：9540k
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
方法3：递归+短路
//递归加短路
public static int Sum_Solution3(int n)
{
int res = n;
/**
拿n=4来举例说明：
当给flag进行赋值操作时，首先判断4>0是true还是false，发现4>0为true，此时并没有办法知道flag为true还是false，所以还要执行&&后面的部分，进行递归：res += Sum_Solution3(n-1)
更小的问题，判断3>0是否正确....
其中flag是设置来让程序不出错，实际上没有意义。(res += Sum_Solution3(n-1))>0)，也是使得程序不出错。
*/
boolean flag = (n>0) && ((res += Sum_Solution3(n-1))>0);
return res;
//运行时间：13ms,占用内存：9204k
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
题目48 不用加减乘除做加法
题目描述：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
分析：
1、首先看十进制是如何做加法的：对于 775+467 1）相加各位的值，不算进位，得到 132； 2）计算进位值，得到进位为：10、100、1000； 3）将进位值与不算进位的值相加，同样使用 (1)、(2) 中先不算进位的方式添加： 132 + 10 100 1000 —————————— 1242 此时各位都没有进位，那么此时不计算进位的值就是最后的结果！ 即计算到没有进位的时候，不计算进位各位相加的值就是最后的结果！ 2、对于二进制，同样是使用这种方法进行加法：对于 1001+1100 1）相加各位的值，不算进位，得到：0101 1001 + 1100 —————————— 0101 可以看出，这种计算就和将二进制的各位做异或运算一样。 2） 计算进位值，得到进位为：10000， 1001 + 1100 —————————— 1000 可以看出，这种计算就和将二进制的各位做与运算，然后将结果左移一位相同！ 3）将进位值与不算进位的值相加，同样使用 (1)、(2) 中先不算进位的方式添加： 0101 + 10000 ———————— 10101 此时各位都没有进位，那么此时不计算进位的值就是最后的结果！ 即计算到没有进位的时候，不计算进位各位相加的值就是最后的结果！！
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
代码如下：
public int Add(int num1,int num2) { // 当进位不为0的时候，说明还不是最后的结果，需要继续相加 while(num2 != 0) { /** * 下一次计算的时候，就是 没有进位的结果 + 进位结果，还是 num1 与 num2的相加， * 我们将 没有进位结果存储到 num1，将进位结果存储到 num2即可 */ //不能直接将 num1^num2 赋予 num1，因为 num1还不能改变，接下来还需参与这一轮的运算。因此用一个临时变量存储。 int temp = num1^num2;//异或，得到当前计算不算进位的结果 // num2可以直接设置为 进位结果，因为num2接下来不需要再参与这一轮的运算 num2 = (num1&num2)<<1;//与运算左移一位，得到当前计算的进位结果，将这个结果存储到num2 num1 = temp;//运算完这一轮，将 没有进位的结果 赋予num1，方便进行下一轮运算 } return num1;//最后的结果存储到 没有进位的结果num1中 }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
题目49 把字符串转换成整数
题目描述：将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。
注：合法的正数字符串只能包含 0-9 以及正负号
+2147483647 合法
1a33 不合法
- 1
- 2
分析：不能使用库函数，那么我们使用 ASCII 码来标记 0-9 这个10个字符。代码如下：
我做的时候牛客网有一个测试用例是 “-2147483649”，要求返回 “-2147483649”。StrToInt 方法的返回值是int类型， 但是java里面int类型只能表示 ："-2147483648" 到 “2147483647” 的数，输入 “-2147483649” 无法表示。因此谁都没有方法使用java通过测试！（知道自己是对的就可以，不需要纠结）
使用 Python 可以解决，因为PYthon的数是动态增加的。这里是java方案，就不贴Python代码了。
public static int StrToInt(String str) { //1、判断字符串是否合法 if(str == null || str.length() == 0) return 0; //2、设置一个变量用于判断符号，默认是正数，当字符串的第一个符号是“-”的时候，才将 isNegative 设置为 true boolean isNegative = false; //这里判断第一位是不是“-”，直接设置值的正负号。这样在循环里面就不需要根据第一位是不是符号来设置值得正负，如果第一位是符号，直接略过即可 if(str.charAt(0) == '-') isNegative = true; //记录结果 long ret = 0;//ret用long表示，防止溢出 for (int i = 0; i < str.length() ; i++) { char c = str.charAt(i); //首先判断第一位是不是正负号，前面已经设置过值得符号，这里如果第一位是正负号，直接略过即可 if(i == 0 && (c == '+' || c == '-')) continue; if(c < '0' || c > '9') return 0;//出现非数字字符（除第一位是正负号情况外），直接返回0（非数字字符串） //数字字符，则求出当前数字字符的值：c-'0'，将前面的ret*10加上这里的值即可 /** 如对于 123，第一次 ret = 0*10 + 1 = 1；第二次 ret = 1*10 + 2 = 12；第三次 ret = 12*10+3 = 123，刚刚好！ */ ret = ret*10 + (c-'0'); //判断是否溢出 if(isNegative == false && ret > Integer.MAX_VALUE) throw new RuntimeException("上溢出"); if(isNegative == true && -ret < Integer.MIN_VALUE ) //这里注意，ret是正数，我们判断其是否下溢出，将其转换为负数与 Integer.MIN_VALUE 相比！ throw new RuntimeException("下溢出"); } return isNegative ? (int)-ret : (int)ret; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
题目50 数组中重复的数字
题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
方法1：从第一个数字开始，对比后面的数字进行查找
这是最笨的方法，就是从第一个数字开始，每次对比后面的数字，当找到重复的，就返回。这种方法的时间复杂度为O(n^2)，空间复杂度为O(1)。虽然可以通过测试，但是性能较差！
public static boolean duplicate1(int numbers[],int length,int [] duplication) { //注意，测试用例有一个空的数组：[]，该数组length=0，因此我们需要提前判断数组为null或者数组长度小于等于0（也可以是等于0） if(numbers == null || length <= 0) { duplication[0] = -1; return false; } for (int i = 0; i < numbers.length ; i++) { for (int j = i+1; j < numbers.length ; j++) { if(numbers[i] == numbers[j]) { duplication[0] = numbers[i]; return true; } } } //如果没有查找到重复的，也必须返回false并使得duplication[0] = -1 duplication[0] = -1; return false; //运行时间：21ms，占用内存：9584k }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
方法2：排序法
利用Arrays类的 sort() 方法对数组进行排序，排序后，判断相邻两个元素是否相等，相等则返回。
//注意，使用这个方法需要在剑指offer上面导入 java.util.Arrays ，否则无法运行 public static boolean duplicate2(int numbers[],int length,int [] duplication) { //同样先排除数组为null或者数组长度为0的情况。 if(numbers == null || length <= 0) { duplication[0] = -1; return false; } Arrays.sort(numbers);//对数组进行排序 //注意！！！，这里i小于length-1，否则遍历到length-1位置，length位置不存在，数组越界 for (int i = 0; i < length-1 ; i++) { if(numbers[i] == numbers[i+1]) { duplication[0] = numbers[i]; return true; } } //没找到重复的 duplication[0] = -1; return false; //运行时间：20ms，占用内存：9656k }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
JDK7以后，对应基本变量数组采用变异的快速排序方法DualPivotQuicksort，对于对象数组比较由原来的mergeSort改为ComparableTimSort方法。TimSort当数组大小小于32时，采用二分插入排序算法，当大于32时，采用基于块-区run的归并排序。所以TimSort是一种二分插入排序和归并排序的变种算法。
对对象进行排序，没有采用快速排序，是因为快速排序是不稳定的，而Timsort是稳定的。与其他合并排序一样，Timesrot是稳定的排序算法，最坏时间复杂度是O（n log n）。在最坏情况下，Timsort算法需要的临时空间是n/2，在最好情况下，它只需要一个很小的临时存储空间。
因此，我们知道这种方法的时间复杂度是 O(nlogn)，空间复杂度是 O(1) 。
方法3 利用HashSet辅助完成
新建一个HashSet，循环数组进行判断：
- 若HashSet中不存在当前元素，则将当前元素加到HashSet中
- 若HashSet中存在当前元素，则说明当前元素为重复元素
由于HashSet中元素 “无序不重复”，利用它不存储重复元素的特性进行操作。
这个方法开辟了一个HashSet，空间复杂度为O(n)，时间复杂度为O(n)。
public static boolean duplicate3(int numbers[],int length,int [] duplication) { //同样先排除数组为null或者数组长度为0的情况。 if(numbers == null || length <= 0) { duplication[0] = -1; return false; } HashSet<Integer> hashSet = new HashSet<>(); for (int number : numbers) { if(!hashSet.contains(number)) {//如果HashSet不包含这个元素，将其添加到HashSet中 hashSet.add(number); }else{ //如果包含，返回这个元素 duplication[0] = number; return true; } } //没找到重复的 duplication[0] = -1; return false; //运行时间：17ms，占用内存：9552k }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
方法4 根据特性
数组的长度为 n 且所有数字都在 0 到 n-1 的范围内，那么数组中每一个下标都有对应的元素。我们可以将每次遇到的数进行"归位"，当某个数发现自己的"位置"被相同的数占了，则出现重复。既可以将值为 i 的元素调整到第 i 个位置上进行求解。
我们从下标为 0 的位置开始，如果当前 i 位置的数字 number[i] 与当前下标 i 不对应，既number[i] != i ，我们就找到当前数字对应的下标位置 number[i]，判断这个位置的数字 number[number[i]] 是否等于 number[i]，如果相等，说明之前有相同的数字占了这个位置，那么这个数字 number[i] 就是重复的数字。如果不相等，就将 number[i] 位置的数字赋值为 number[i]，既number[ number[i] ] = number[i]。
随后再判断 当前 i 位置的数字 number[i] 与当前下标 i 是否对应，如果不对应，继续按上面的规则进行交换！注意，必须换到 当前 i 位置的数字 number[i] 与当前下标 i 相等，才能使得 i+1 进行下一轮的判断，这种换法保证当前位置以及之前的所有位置的下标与数字都相同！否则可能出现某个位置 i 与它对应的数字 number[i] 不相等的情况。（此处使用while，不使用if）
我们这一从数组开头一直找到结尾，由于所有数字都有对应的下标，如果没有重复，最后所有的数字都会回到它对应的位置。如果中间某一个数重复，在第二次将它移动到它对应下标位置时，就会发现它是重复的数字！
- 代码里面：for循环保证所有下标都可以换到；while循环保证当前下标以及前面所有的下标与它的元素都是相等的。这两个合起来保证所有的下标都可以判断到！！！
对于元素无序的数组，我们无法使用这种方法。因为我们不知道应该将当前元素与哪个位置的元素作比较！
package com.lkj; import java.util.Arrays; import java.util.HashSet; public class OfferGetTest50 { public static boolean duplicate4(int numbers[],int length,int [] duplication) { //同样先排除数组为null或者数组长度为0的情况。 if(numbers == null || length <= 0) { duplication[0] = -1; return false; } for (int i = 0; i < length ; i++) { /* 如果当前 i 位置的数字 number[i] 与当前位置下标 i 不对应，我们将数字numbers[i]移动到它对应的下标位置， 既将 number[i] 位置的数字与 i 位置的数字互换。如果交换后 i 位置的数字仍然与 i 不相等，继续换， 必须换到 当前 i 位置的数字 number[i] 与当前下标 i 相等，才能使得 i+1 进行下一轮的判断， 这种换法保证当前位置以及之前的所有位置的下标与数字都相同！ 否则可能出现某个位置 i 与它对应的数字 number[i] 不相等的情况。（因此此处使用while，不使用if） */ while(numbers[i] != i) { //numbers[i]与它对应的下标位置的元素相等，说明之前有相同的数字占了这个位置，那么这个数字 number[i] 就是重复的数字 if(numbers[i] == numbers[numbers[i]]) { duplication[0] = numbers[i]; return true; } else { //numbers[i]与它对应的下标位置的元素不相等，将 number[i] 位置的数字与 i 位置的数字互换。 // int temp = numbers[i]; // numbers[i] = numbers[numbers[i]]; // numbers[numbers[i]] = temp; /** * 注意！！！这里互换这里很容易出错！！按下面的测试用例分析 * 比如当 i=0 的时候，第一行将numbers[0]=2 赋予temp=2，第二行 numbers[0] = numbers[numbers[0]] ，既numbers[0] = numbers[2]=1。 * 最后第三行我们是想将之前index=0的位置的数字赋予index=2的位置，但是此时 * numbers[0] = 1，变成 numbers[1] = temp = 2，其实应该是 numbers[2] = temp = 2. * * 之所以会出错，是因为第二行的时候 numbers[0] 的值改变了，不再是2，而是1，而后面我们使用 numbers[numbers[0]] = temp ， * 原先是想 numbers[2] = temp ，由于numbers[0] 的值改变了，变成 numbers[1] = temp。因此出错。 * * 那么，此处最开始 numbers[i] 的值赋予 temp，我们使用 temp 来作为数组下标，因为 numbers[i] 变化了，但是 temp 没有变化， * 此时 numbers[numbers[i]] = temp 改为 numbers[temp] = temp ，numbers[temp]中的temp是原来的 numbers[i]， * 这样就会正确赋值。（一切都是因为第二行的时候 numbers[0] 的值改变了） * */ //int temp = numbers[i]; //numbers[i] = numbers[temp]; //numbers[temp] = temp; //其实这里写为一个swap()函数，就不需要思考这些角标的问题 swap(numbers , numbers[i] , i); } } } //遍历完没找到重复的 duplication[0] = -1; return false; /* 运行时间：21ms，占用内存：9576k 复杂度分析： 从宏观上来看，虽然代码中有2个循环，但是所有的操作都只是把某个位置的元素移动到它对应的位置， 既如果有n个数字，最多操作n次可以将他们移动到他们对应来的位置。因此次方法时间复杂度为O(n)，空间复杂度为O(1)。 */ } private static void swap(int[] arr , int m , int n) { int temp = arr[m]; arr[m] = arr[n]; arr[n] = temp; } public static void main(String[] args) { int[] nums = new int[]{2, 3, 1, 0, 2, 5}; int n = nums.length; int[] dup = new int[1]; boolean flag = duplicate4(nums, n, dup); System.out.println(flag + "," + dup[0]); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
复杂度分析：从宏观上来看，虽然代码中有2个循环，但是所有的操作都只是把某个位置的元素移动到它对应的位置， 既如果有n个数字，最多操作n次可以将他们移动到他们对应来的位置。因此次方法时间复杂度为O(n)，空间复杂度为O(1)。
下面是交换过程中一些细节的分析。
