剑指offer03：数组中重复的数字

题目

题目链接

剑指Offer：数组中重复的数字

题目描述

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

分析

首先本题要清楚题目的要求：

• 先对数组进行排序，然后再查找排序后的数组中的重复元素

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            return false;
        }
        Arrays.sort(numbers);
        for (int i = 0; i < length - 1; i++) {
            if (numbers[i + 1] == numbers[i]) {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;
    }
}

• 从头到尾依次扫描数组中每一个数字。当扫描到第i个元素时，比较该位置数值m是否等于i。若是，接着扫描下一个数字；否则，将其与第m个数字进行比较。若相等，则返回该重复数字；否则，交换两个数字，继续重复前面的过程。

  数组的长度为 n 且所有数字都在 0 到 n-1 的范围内，我们可以将每次遇到的数进行"归位"，当某个数发现自己的"位置"被相同的数占了，则出现重复。
  扫描整个数组，当扫描到下标为 i 的数字时，首先比较该数字（m）是否等于 i，如果是，则接着扫描下一个数字；如果不是，则拿 m 与第 m 个数比较。如果 m 与第 m 个数相等，则说明出现重复了；如果 m 与第 m 个数不相等，则将 m 与第 m 个数交换，将 m "归位"，再重复比较交换的过程，直到发现重复的数

  举个栗子：
  以数组 {2,3,1,0,2,5,3} 为例
  当 i = 0 时，nums[i] = 2 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{1,3,2,0,2,5,3}
  此时 i = 0，nums[i] = 1 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{3,1,2,0,2,5,3}
  此时 i = 0，nums[i] = 3 != i，判断 nums[i] 不等于 nums[nums[i]]，交换 nums[i] 和 nums[nums[i]]，交换后数组为：{0,1,2,3,2,5,3}
  此时 i = 0，nums[i] = 0 = i，继续下一组
  当 i = 1，nums[i] = 1 = i，继续下一组
  当 i = 2，nums[i] = 2 = i，继续下一组
  当 i = 3，nums[i] = 3 = i，继续下一组
  当 i = 4，nums[i] = 2 != i，判断 nums[i] 等于 nums[nums[i]]，出现重复，赋值返回

public class Solution {
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            return false;
        }
        for (int i = 0; i < length; i++) {
            while (numbers[i] != i) {
                if (numbers[i] == numbers[numbers[i]]) {
                    duplication[0] = numbers[i];
                    return true;
                }
                int tmp = numbers[i];
                numbers[i] = numbers[tmp];
                numbers[tmp] = tmp;
            }
        }
        return false;
    }
}

• 利用 HashSet或辅助数组 解决，从头到尾扫描数组，每次扫描到一个数，判断当前数是否存在 HashSet 中，如果存在，则重复，对 duplication 赋值返回，否则将该数加入到 HashSet 中。

public class Solution {
    //利用 HashSet 解决，从头到尾扫描数组，每次扫描到一个数，判断当前数是否存在 HashSet 中，如果存在，
    //则重复，对 duplication 赋值返回，否则将该数加入到 HashSet 中
    public boolean duplicate(int numbers[], int length, int[] duplication) {
        if (numbers == null || length <= 0) {
            return false;
        }
        Set set = new HashSet();
        for (int i = 0; i < numbers.length; i++) {
            if (set.contains(numbers[i])) {
                duplication[0] = numbers[i];
                return true;
            }else {
                set.add(numbers[i]);
            }
        }
        return false;
    }
}

扩展：

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。从数组中找出任意一个重复的数字，但不能修改输入的数组。如{2,3,5,4,3,2,6,7}得到2或者3.

• 在数字 1~n 中取中间值 m = (1+n) / 2, 此时数字包括 1~m, m+1~n 两段；
  遍历数组，获得数字 1~m 的个数;
  如果数字 1~m 的个数大于 m，说明 1~m 这一段内肯定有重复数字，那么在这一段内继续取中间值比较；
  如果数字 1~m 的个数等于 m，这一段不一定有重复数字，比较后一段；
  如果数字 1~m 的个数小于 m，说明 m+1~n 这一段一定有重复数字，在后一段取中间值比较；
  按照上述方法一直取中间值比较，直到只剩一个数字且这个数字出现次数超过 1 ，该数字即为重复数字

public class Other {
    /**
     * 
     * 1）把1~n的数字从中间的数字m分为两部分，前面一半为1~m，后面一半为m+1~n
     *
     * 2）如果1~m这部分的数字对应数组里的值超过m个，这个区间就包含有重复的数字，否则就是另外一个区间包含重复的数字。就算两个区间都有重复的也只要再对某一个区间进行二分，因为题目要求只要找到任意一个重复的数字
     *
     * 3）继续把重复数字的区间进行二分，直到找到一个重复的数字
     */
    /**
     * int mid = (start+end)/2可能会溢出，用>>是遇到负奇数的时候求上下界统一
     * -5/2=-2   5/2=2   上下界求法不统一
     * -5>>1=-3  5>>1=2  统一
     */
    int getDuplication(int[] numbers, int length) {

        int start = 1;
        int end = length - 1;
        while (end >= start) {

            int mid = start + (end - start) >> 1;
            int count = countRange(numbers, length, start, mid);
            if (end == start) {
                if (count > 1) {
                    return start;
                }
                break;
            }
            if (count > (mid - start + 1)) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return -1;
    }

    int countRange(int[] numbers, int length, int start, int end) {
        int count = 0;
        for (int i = 0; i < length; i++) {
            if (numbers[i] >= start && numbers[i] <= end) {
                ++count;
            }
        }
        return count;
    }
}

Q.E.D.