面试题3: 数组中重复的元素

package cn.zxy.interview;

/**
 *
 * 问题一分析:
 * 1. 数组长度为n, 也就是说有n个位置; 数字在0~n-1范围内, 每个数都能放到数组特定的位置, 比如数字2放到索引为2的地方, 如果有两个2,
 * 相同位置就会出现重复的数字.
 *
 * 步骤:
 * 1. 遍历数组, 遍历到下标为i的数字x, 判断该数x是不是i
 * 2. 如果是, 判断下一个
 * 3. 如果不是, 访问以该数作为下标的元素y, 判断x的值是否与y相等
 * 4. 如果相等, 找到了重复元素;
 * 5. 如果不等, 交换x, y
 * 6. 下一个
 *
 *
 * 问题二分析:
 * 给定数组长度n+1, 数字范围为1~n, 一定会重复的原因是, 1~n不重复的数一遍共有n个数字, 想填满数组的n+1个位置, 必定有一个重复
 * 二分法: 以数字在1~7为例, 取一半的范围, 也就数1~4, 看看重复的数字在不在这个范围里, 怎么知道呢?
 * 遍历数组, 如果在1~4范围内有5或5个以上数字, 那么就在这个范围内; 反之, 就在5~7的范围内
 * 在新范围内继续二分查找, 直到start==end
 *
 */

public class A03_RepeatNumber {
    public static int findRepeatNumber(int[] a){
        // 空数组, 直接返回
        if(a == null) return -1;
        for (int i = 0; i < a.length; i++) {
            // 元素大小超出0~n-1, 返回-1
            if(a[i] >= a.length || a[i] < 0 ) return -1;
            if(a[i] == i){
                continue;
            } else {
                int y = a[a[i]];
                if(a[i] == y){
                    return a[i];
                }else{
                    swap(a, i, a[i]);
                }
            }
        }
        // 没有重复元素 返回-1
        return -1;
    }

    // 问题二
    // 例如, n=7, 数组长度为8, 元素为1~7
    public static int findRepeatDontModify(int[] a){
        if(a == null || a.length == 0) return  0;

        int start = 1;
        int end = a.length-1;
        while(start <= end){
            int mid = ((end - start) >> 1) + start;
            int count = countRange(a, start, mid);
            // 循环结束
            if(start == end){
                if(count > 1){
                    return start;
                }else{
                    break;
                }
            }

            int range = mid - start + 1;
            if (count > range){
                // 在前半段 收缩end到mid
                end = mid;
            }else{
                start = mid + 1;
            }
        }


        return -1;
    }

    private static int countRange(int[] a, int start, int mid) {
        int count = 0;
        for (int i = 0; i < a.length; i++) {
            if (a[i] >= start && a[i] <= mid){
                count++;
            }
        }
        return count;
    }

    private static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    public static void main(String[] args) {
        int[] a1 = {3, 3, 1, 0, 2, 5, 3};
        int[] a2 = {3, 1, 4, 0, 5, 2 };
        int[] a3 = null;
        int num = findRepeatNumber(a3);
        System.out.println(num);

        // 问题二
        int[] b1 = {4, 2, 3, 1, 5, 6, 7, 2};
        int[] b2 = {1,2,3,4,5};
        int[] b3 = null;
        int num2 = findRepeatDontModify(b2);
        System.out.println(num2);
     }
}