找出长度为n的数组中重复的数字(数字范围在0~n-1)

超、凢脫俗 2022-05-14 23:29 167阅读 0赞

分析：对这个数组进行排序，若没有重复的数字的话数组i位置的值为i。依照这个思路，可以遍历该数组：首先判断数组i位置的值m是否等于i,若相等则判断下一位置对应的数字；若不相等，则判断m是否与位置m处对应的值是否相等。若相等，则说明位置i处的值与位置m处的值相等，m即为数组中的一个重复数字，返回该值即可；若不相等，则将m放到位置m处（即将i位置的数字与m位置的数字交换）,从数组位置i处继续判断，直至结束。

代码如下：

/**
     *   功能描述：找出长度为n的数组中重复的数字(数字范围在0~n-1) 
     * @author  liuhao 
     * 
     * @date 2018年8月20日 上午9:19:14 
     * @version 1.0 
     * @parameter  
     * @since  
     * @return  
     */
    public class Duplicate {
    
    	public static int ans = -1;
    
    	public static void main(String[] args) {
    //		int[] nums = { 2,3,1,0,2,5,3};
    		int[] nums = { 1,2,4,3,1};
    		System.out.println(findDuplicate(nums));
    		if (findDuplicate(nums)) {
    			System.out.println(ans);
    		}
    	}
    
    	public static boolean findDuplicate(int[] nums) {
    		if (nums == null || nums.length <= 0) {
    			return false;
    		}
    		for (int i = 0; i < nums.length; i++) {
    			if (nums[i] < 0 || nums[i] > nums.length - 1) {
    				return false;
    			}
    		}
    		for (int i = 0; i < nums.length; ) {
    			if (nums[i] != i) {
    				if (nums[i] == nums[nums[i]]) {
    					ans = nums[i];
    					return true;
    				}
    				int temp = nums[i];
    				nums[i] = nums[temp];
    				nums[temp] = temp;
    			}else {
    				i++;
    			}
    		}
    		return false;
    	}
    
    }