日常刷题之剑指offer：3.数组中重复的数字

不念不忘少年蓝@ 2022-11-30 15:57 116阅读 0赞

# 一、题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。 #

# 二、解题思路 #

## 1.暴力法：直接排序，然后看相邻两个数是否相同，相同则为重复（此题暴力无法AC） ##

## 2.时间复杂度和空间复杂度均为O(n)，用一个map来将数组的值作为key存储，一次for循环即可，每次先判断map.containsKey(numbers\[i\])，如果为true则直接返回；如果为false则将numbers\[i\]作为key存储到map中 ##

public boolean duplicate(int[] numbers, int length, int[] duplication) { 
    	Map<Integer,Object> map = new HashMap<>();
    	for(int i = 0; i < length; i++) { 
    		if(map.containsKey(numbers[i])) { 
    			duplication[0] = numbers[i];
    			return true;
    		}
    		map.put(numbers[i],new Object());
    	}
    	return false;
    }

## 3.时间复杂度为O(n)，空间复杂度为O(1)，注意题干说长度为n的数组中数字在0~n-1，这样就刚好数值都在数组下标范围内，所以可以将数值与坐标对应起来，即数值0就放到下标为0的位置，以此类推。本题是找出随便一个重复数值，那么当数值为n要放置的下标n已经有一个相等的值则为重复 ##

public boolean duplicate(int[] numbers, int length, int[] duplication) { 
    	for(int i = 0; i < length; i++) { 
    		while(numbers[i] != i) { 
    			if(numbers[i] == numbers[numbers[i]]) { 
    				duplication[0] = numbers[i];
    				return true;
    			}
    			swap(numbers,i,numbers[i]);
    		}
    	}
    	return false;
    }
    public void swap(int[] numbers, int i, int j) { 
    	numbers[i] = numbers[i]^numbers[j];
    	numbers[j] = numbers[i]^numbers[j];
    	numbers[i] = numbers[i]^numbers[j];
    	/** 上面通过异或可以不需要临时变量实现两数交换 int temp = numbers[i]; numbers[i] = numbers[j]; numbers[j] = temp; **/
    }