剑指Offer面试题03－找出数组中重复的数字(5种方法)

﹏ヽ暗。殇╰゛Y 2023-02-13 00:29 6阅读 0赞

题目：

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
    
    示例 1：
    输入：
    [2, 3, 1, 0, 2, 5, 3]
    输出：2 或 3
    
    限制：2<=n<=100000

题目很好理解，没有什么需要分析的部分．既然n个数字,范围却是0~n-1,肯定有重复的.

### 一.统计个数 ###

题目是为了找重复的数字，最简单的方法就是把他们出现的次数都统计出来，结果大于１的，自然就是重复了．像桶排序一样，先创建桶，这里是下标，因为正好给定的数组的元素个数是 n ,数值范围是 0 ~ n-1.那么就可以用下标代表某个数字,然后对应的值来代表出现的个数.

class Solution {
        
        public int findRepeatNumber(int[] nums) {
        
        	//新建一个数组,下标代表原数组中的元素,因此下标只需要到n-1
            int[] count=new int[nums.length];
            int ans=0;
            for(int i:nums){
        
                if(count[i]==0){
        
                    count[i]++;
                }else{
        
                    ans=i;
                    break;
                }
            }
            return ans;
        }
    }

时间复杂度和空间复杂度都是O(n),因为遍历了整个容量为n的数组,还创建了一个新的容量为n的数组.

### 二.利用哈希表 ###

正好java里面提供了HashSet集合,特点就是元素不能重复,当我们加入重复元素的时候,add方法无法运行成功，那么就代表当前数字是重复的了．

class Solution{
        
    	public int findRepeatNumber(int[] nums){
        
    		HashSet<Integer> set=new HashSet<>();
    		int ans=0;
    		for(int num: nums){
        
    			if(!set.add(num)){
        
    				ans=num;
    				break;
    			}
    		}
    		return ans;
    	}
    }

这种方法涉及到一个HashSet底层会自己扩容,因此时间复杂度应该会更高一些.

### 三.排序 ###

先排序，有序之后只需要比较相邻的每两个元素，总会遇到相同的，那么就可以得到答案

class Solution{
        
    	public int findRepeatNumber(int[] nums){
        
    		Arrays.sort(nums);
    		for(int i=0;i<nums.length-1;i++){
        
    			if(nums[i]==nums[i+1]){
        
    				return nums[i];
    			}
    		}
    		return -1;
    	}
    }

这个方法的时间复杂度是内部排序方法的时间复杂度＋遍历一遍数组的时间复杂度．

### 四.一般想不到的：原地置换，将原数组作为哈希表 ###

这个方法的重点是利用题目信息给的：长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内,这样一来,本来这个数组就可以作为一个哈希表,但是其中有某几个元素捣乱了.

那么，对于这个乱序的数组，从头开始遍历，每当遍历到一个数字 nums\[i\] ,如果他不等于i, (也就是他并不在自己应该在的哈希表的位置).  
我们就把他放到应该在的位置去,也就是把他和 nums\[nums\[i\]\] 进行交换．

只要一直这么换换换…就一定会发生一个情况,就是要交换的这两个数字是一样的.因为有重复,当别的错位元素都回归自己本该在的位置时,重复元素肯定会被剩下来.此时我们就将他返回,就是我们要的答案.

class Solution{
        
    	public int findRepeatNumber(int [] nums){
        
    		int temp=0;
    		for(int i=0;i<nums.length;i++){
        
    			while(nums[i]!=i){
        
    				if(nums[i]==nums[nums[i]]){
        
    					return nums[i];
    				}
    				temp=nums[i];
    				nums[i]=nums[temp];//一样是交换,用temp省事
    				nums[temp]=temp;
    		}
    		return -1;
    	}
    }

这个方法时间复杂度应该是O(n),在一次遍历里面,只需要常数次的交换.

### 五.暴力双重循环 ###

比较是否一样,那就比就完事了…

class Solution{
        
    	public int findRepeatNumber(int[] nums){
        
    		for(int i=0;i<nums.length;i++){
        
                for(int j=0;j!=i&&j<nums.length;j++){
        
                    if(nums[i]==nums[j]){
        
                        return nums[i];
                    }
                }
            }
            return -1;
    	}
    }

时间复杂度O(n2).

力扣的评论区的weiwei大佬说，这个题发挥空间很大，因为边界条件种种并没有给定，因此面试即使遇到应该也要自己主动去考虑，去和面试官讨论。

##### 比如：是否可以修改原数组？（方法4就修改了原数组）是否可以使用额外存储空间？（除了方法4和5，都用了额外存储空间） #####

--------------------

补充  
第二天又做到了另一个题目,因此给这道题提供了思路，一个是二分法，另一个是快慢指针，二分法是用时间换空间，时间复杂度比较高，快慢指针是用Floyd找环的方法．不过针对这道题给定的数字范围，是不能用Floyd方法的，原因是这道题有０，在进行判环的时候，如果nums\[0\]=0,本身就是死循环的.  
另外一个题目的解法指路下一篇博客：  
https://blog.csdn.net/weixin\_42092787/article/details/106365406