今天应该继续讲讲Android系统的知识,但是发现内容有点多,说不完??。嗯,为了保证文章质量,我今天把一道算法题顶上去~??面试中也经常考算法题。前面说过,虽然用得少,但是从算法题上可以检验一个程序员的基本逻辑思维。今天来看看简知Offer上的一道题:数组中重复的数字。题目:数组中重复的数都是0到n-1范围内长度为n的数组nums中的数。数组中有些数字是重复的,但是不知道重复了多少个数字,也不知道每个数字重复了多少次。请找出数组中任何重复的数字。例1:输入:[2,3,1,0,2,5,3]输出:2or3限制:2<=n<=100000分析题后,主要目的是找出其中重复的数字大批。所以我们可以使用那些没有重复且成员唯一的集合,比如HashSet。HashSet的特点是唯一和无序的,所以只要我们把数组中的数字加到HashSet中,如果有重复的数字,就会加法失败。使用它来完成解决方案。classSolution{publicintfindRepeatNumber(int[]nums){Setset=newHashSet();intrepeat=-1;for(intnum:nums){if(!set.add(num)){repeat=num;break;}}returnrepeat;}}代码比较简单,设置一个空的HashSet集合,然后将数字一个一个地添加进去,如果失败(即add方法返回false),则表示数字被重复。方法消耗执行时间:6ms内存消耗:48.3MB时间复杂度由于使用了for单循环,复杂度为O(n),其他代码复杂度为O(1),包括set.add的复杂度也是O(1)。所以总的时间复杂度是O(n)。空间复杂度如果set集合加一次,就占用一次空间,所以循环n次,最坏情况空间复杂度为O(n)解2这道题其实有个问题不好找,就是第一句话:长度为n的数组nums中的所有数字都在0到n-1的范围内。这句话的意思是,如果没有重复的数字,排序后的数组要下标为i。该位置的值应等于i。即nums[i]=i。比如数组的长度是5,那么里面的数字应该在0到4之间,如果没有重复的数字,那么排序后的数组应该是:[0,1,2,3,4]即nums[i]=i,根据这个特性,我们可以把数字依次对应数字,通常来说,一个数字对应多个坑,即一个胡萝卜和一个坑。当发现一个坑里有两个萝卜时,有重复的数字。上面的代码:[nums[i]]){returnnums[i];}temp=nums[i];nums[i]=nums[temp];nums[temp]=temp;}}return-1;}}简单地说:遍历数组,当发现数组的下标数不等于下标对应的数,即nums[i]!=i,那么我们把nums[i]的数放到nums[i]的位置,直到nums[i]==i。每个坑一个萝卜,所以当你的坑被同一个萝卜(编号)占据时,这个萝卜就是重复的编号。如果i=0时数组为[3,1,4,2,2],则nums[i]=3。3!=1。所以把3放在num[3]的位置,数组就变成了[2,1,4,3,2]。2!=0,条件为真,继续替换,数组变为[4,1,2,3,2]。4!=0,条件为真,继续替换,数组变为[2,1,2,3,4]。2!=0,虽然条件为真,但是此时2位置的坑已经被同一个数占用,所以这个2就是重复数,返回。方法消耗执行时间:0-1ms内存消耗:46.4MB时间复杂度有一个for循环,复杂度为O(n),但是在循环中,while最多可能出现n次替换,其实是一个排序过程。但是这个while排序只会发生一次。如果最多发生n次,说明以后不需要排序了。所以复杂度是O(n+n),也就是O(n)。在空间复杂度上,由于使用了原来的数组,只多了一个变量temp,所以空间复杂度为O(1)。我也会偶尔练习几道算法题,因为我自己做的算法题不多,所以如果有不对的地方或者有什么需要讨论的,可以在讨论群里发表自己的看法。谢谢你们。参考https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof/