[数据结构与算法]6.寻找重复数

解题思路

HashMap来保存数组中的值和出现的次数

    public int findDuplicate(int[] nums){
        int count = 1 ;
        HashMap<Integer,Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if(map.containsKey(nums[i])){
                return nums[i];
            }
            map.put(nums[i],count);
        }
        return -1;
    }

Set集合进行去重操作

    public int findDuplicate2(int[] nums){
        HashSet<Integer> set = new HashSet();
        for (int i = 0; i < nums.length; i++) {
            if(set.contains(nums[i])){
                return nums[i];
            }
            set.add(nums[i]);
        }
        return -1;
    }

数组排序+找到前后相同的值

 public int findDuplicate3(int[] nums){
        Arrays.sort(nums);
        //遍历元素，遇到前后相同，即为重复数字
        for (int i = 0; i < nums.length; i++) {
           if(nums[i]==nums[i+1])
           {
               return nums[i];
           }
        }
        return -1;
    }

二分查找原始的1-N序列

规律：

• 以target为界，对于比target小的数num，数组中所有小于等于它的数，最多出现一次（有可能被多出现的target占用了），所以总个数不会超过num。
• 对于比target大的数num，如果每个元素都只出现一次，那么所有小于等于它的元素是num个；而现在target会重复出现，所以总数一定会大于num。

    public int findDuplicate4(int[] nums){
        //对1-N的序列进行二分查找。
        int left = 1;
        int right = nums.length - 1;
        while (left<=right){
            int mid = (left+right)/2;
            int count = 0;
            //统计每个数出现的次数
            for (int i = 0; i < nums.length; i++) {
                if(nums[i]<=mid){
                    count++;
                }
            }
            //对于target小的数字来说，统计出来小于i的个数，应该是小于等于i的大小。
            if(count <= mid){
                left = mid + 1;
            }
            //对于target大或者target的数字来说，统计出来小于i的个数，应该是大于i的大小。
            else if(count>mid){
                right = mid ; //可能mid为target/比target大
            }
            // 左右指针重合时，找到target
            if(right == left){
                return left;
            }
        }
        return -1;
    }

快慢指针

思路

这是一种比较特殊的思路。把nums看成是顺序存储的链表，nums中每个元素的值既是下一个链表节点的地址，也是当前链表的值。

步骤

第一阶段，寻找环中的节点
a)初始时，都指向链表第一个节点nums[0]；
b)慢指针每次走一步，快指针走两步；
c)如果有环，那么快指针一定会再次追上慢指针；相遇时，相遇节点必在环中
第二阶段，寻找环的入口节点（重复的地址值）
d)重新定义两个指针，让before，after分别指向链表开始节点，相遇节点。
e)before与after相遇时，相遇点就是环的入口节点。

数学分析

慢指针总路程 = 环外0到入口 + 环内入口到相遇点 (可能还有 + 环内m圈)
快指针总路程 = 环外0到入口 + 环内入口到相遇点 + 环内n圈
并且快是慢的两倍。
环内n-m圈 = 环外0到入口 + 环内入口到相遇点（环内一圈——相遇点到入口）。
环内相遇点到入口 + 环内n-m-1圈 = 环外0到入口
所以第二次分别从开始和相遇点出现，就能找到环的入口结点。

public int findDuplicate(int[] nums){
    // 定义快慢指针
    int fast = 0, low = 0;
    // 第一阶段：寻找链表中的环
    do {
        // 快指针一次走两步，慢指针一次走一步
        low = nums[low];
        fast = nums[nums[fast]];
    } while( fast != low); 

    // 第二阶段：寻找环在链上的入口节点
    int ptr1 = 0, ptr2 = low;
    while( ptr1 != ptr2 ){
        ptr1 = nums[ptr1];
        ptr2 = nums[ptr2];
    }
    return ptr1;
}