题解 | #数组中重复的数字#

方案一:

Java代码:

class Solution {
    public int duplicateInArray(int[] nums) {
        // 如果输入数组是空, 直接返回-1
        if (nums.length == 0) return -1;
        
        // 创建aa数组, 长度是 n
        int aa[] = new int[nums.length];
        for (int i = 0; i<nums.length; i++){
            if (nums[i] < 0 || nums[i] > (nums.length-1)) return -1;
            aa[nums[i]] ++;
        }
        for (int i=0; i<nums.length; i++){
            if (aa[i] > 1) return i;
        }
        return -1;
    }
}

解题思路:

因为输入的是数组, 并且数组中元素在 0-n-1之间,

因此直接设 一个新的数组 aa, 长度为n, 这样nums数组中的元素大小对应于 aa数组的索引,

当 nums 中出现该元素, 对应aa数组的索引位置+1,

最后遍历 aa 数组, 当值大于2时, 说明该索引在 nums 数组中出现的次数多于1次, 返回 索引值

需要注意:

输入数组是空, 直接返回 -1

nums中的数组元素 不满足 [0, n-1] 的条件, 直接返回-1

方案二：

Java代码

class Solution {
    public int duplicateInArray(int[] nums) {
        // 方法2：
        int n = nums.length;
        if (n==0) return -1; 
        // 进行数组扫描
        for (int i=0; i<n; i++){
            // 如果 nums 数组中的元素不满足条件, 则返回-1
            if (nums[i] < 0 || nums[i] > (n-1)) return -1;
        }
    
        
        for (int i=0; i<n; i++){
            // 将nums数组中的每一个元素放入对应的索引中        
            while(nums[i] != nums[nums[i]]) {
                // swap(nums[i], nums[nums[i]]);
                // 进行交换
                int x = nums[i];
                // 将 每一个元素放入对应的索引中
                nums[i] = nums[nums[i]];
                nums[x] = x;
            }
            // 循环结束的情况:
            // 1. nums[0]=0, 即第i个索引位置 正好是元素i, 则进入下一个for循环 i++
            // 2. nums[0]=x, and nums[x] =x, 说明第x个索引位置正好是元素x, 并且因此 nums[0]=x, 说明x元素不止一个
            if (nums[i] != i) return nums[i];
            
        }
        
        return -1;
    }
}

解题思路

将 每一个元素nums[i] 放入到 对应的索引位置

当 索引为 nums[i] 的位置的元素不等于 nums[i], 则将其两者交换