287.寻找重复数，双指针，二分查找

linwt · linwt · commit 7ccf337bb29a · 2022-04-16T19:46:09.000+08:00
diff --git a/leetcode_Java/DoneTitle.txt b/leetcode_Java/DoneTitle.txt
@@ -88,6 +88,7 @@
 239. 滑动窗口最大值
 279. 完全平方数
 283. 移动零
+287. 寻找重复数
 300. 最长上升子序列
 303. 区域和检索 - 数组不可变
 304. 二维区域和检索 - 矩阵不可变
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -153,6 +153,7 @@
 215. 数组中的第K个最大元素
 239. 滑动窗口最大值
 283. 移动零
+287. 寻找重复数
 303. 区域和检索 - 数组不可变
 304. 二维区域和检索 - 矩阵不可变
 406. 根据身高重建队列
diff --git a/leetcode_Java/Solution0142.java b/leetcode_Java/Solution0142.java
@@ -55,7 +55,7 @@ public ListNode detectCycle(ListNode head) {
 快慢指针：
 1、慢指针走一步，快指针走两步
 2、如果没有环，则快指针会走到空指针
-3、如果有环，假设在环中，以快指针为起点，快指针距离慢指针n步，那么当慢指针走n步后的位置为2n，刚好快指针也走2n步，所以会快慢指针会相遇
+3、如果有环，假设在环中，以快指针为起点，快指针距离慢指针n步，那么当慢指针走n步后的位置为2n，刚好快指针也走2n步，所以快慢指针会相遇
 4、入环口位置分析：
   1）设非环部分长度为a，环部分长度为b，快慢相遇时，慢指针走了s，快指针走了2s，快指针比慢指针多走了n次b，所以2s=s+nb，即s=nb
   2）从链表头部走到入环口需要a+nb步。即走a步到了入环口，每绕一圈b步都会回到入环口
diff --git a/leetcode_Java/Solution0287.java b/leetcode_Java/Solution0287.java
@@ -0,0 +1,95 @@
+// 287. 寻找重复数
+
+
+/*
+哈希表：记录遍历过的数，如果当前数已存在于哈希表中，则该数是重复数
+ */
+class Solution {
+    public int findDuplicate(int[] nums) {
+        Map<Integer, Boolean> map = new HashMap<>();
+        for (int num : nums) {
+            if (map.getOrDefault(num, false)) {
+                return num;
+            }
+            map.put(num, true);
+        }
+        return -1;
+    }
+}
+
+
+/*
+快慢指针，思路同“142.环形链表II”
+1、如果数组中有重复的数，以数组 [1,3,4,2,2] 为例,我们将数组索引 n 和数 nums[n] 建立一个映射关系 f(n)，其映射关系 n->f(n) 为：
+    元素： 1  3  4  2  2
+    索引： 0  1  2  3  4
+    0->1  1->3  2->4  3->2  4->2
+2、我们从索引为 0 出发，根据 f(n) 计算出一个值，以这个值为新的索引，再用这个函数计算，以此类推产生一个类似链表一样的索引序列
+    0  →  1  →  3  →  2  →  4
+                      ↑_____↓
+3、将问题转化成环形链表
+  1）数组中有一个重复的整数 <==> 链表中存在环
+  2）找到数组中的重复整数 <==> 找到链表的环入口
+4、快慢指针走法
+  1）慢指针走一步 slow = slow.next <==>  slow = nums[slow]
+  2）快指针走两步 fast = fast.next.next <==>  fast = nums[nums[fast]]
+ */
+class Solution {
+    public int findDuplicate(int[] nums) {
+        int slow = 0, fast = 0;
+        do {
+            slow = nums[slow];
+            fast = nums[nums[fast]];
+        } while (slow != fast);
+        int pre = 0;
+        while (slow != pre) {
+            slow = nums[slow];
+            pre = nums[pre];
+        }
+        return slow;
+    }
+}
+
+
+/*
+二分查找：
+1、数字在[1,n]范围内，初始化left为1，right为n。所有计算都是用数字，没用到索引
+2、找中间数mid，计算数组中小于等于mid的元素数量，如果数量大于mid说明重复元素在区间[left,mid]，否则重复元素在区间[mid+1,right]
+3、循环二分查找，直到找到重复元素
+
+数组：[1,3,2,5,2,4]
+  1   2   3   4   5
+left     mid    right
+count=4 > mid=3
+======================
+  1   2   3   4   5
+left mid right
+count=3 > mid=2
+======================
+    1      2   3   4   5
+left/mid right
+count=1 !> mid=1
+======================
+  1      2      3   4   5
+     left/right
+ */
+class Solution {
+    public int findDuplicate(int[] nums) {
+        int left = 1, right = nums.length - 1;
+        while (left < right) {
+            int mid = (left + right) / 2;
+            int count = 0;
+            for (int num : nums) {
+                if (num <= mid) {
+                    count++;
+                }
+            }
+            if (count > mid) {
+                right = mid;
+            } else {
+                left = mid + 1;
+            }
+        }
+        return left;
+    }
+}
