287.寻找重复数，位运算

linwt · linwt · commit 60b639f1ff9f · 2022-04-16T21:22:48.000+08:00
diff --git a/leetcode_Java/DoneType.txt b/leetcode_Java/DoneType.txt
@@ -153,7 +153,7 @@
 215. 数组中的第K个最大元素（快速排序，堆排序）
 239. 滑动窗口最大值（单调递减双端队列）
 283. 移动零（双指针）
-287. 寻找重复数（哈希表，快慢指针，二分查找）
+287. 寻找重复数（哈希表，快慢指针，二分查找，位运算）
 303. 区域和检索 - 数组不可变（前缀和）
 304. 二维区域和检索 - 矩阵不可变（前缀和）
 406. 根据身高重建队列（二维数组排序）
@@ -173,6 +173,7 @@
 
 
 九、位运算
+287. 寻找重复数
 338. 比特位计数
 461. 汉明距离
 
diff --git a/leetcode_Java/Solution0287.java b/leetcode_Java/Solution0287.java
@@ -92,4 +92,52 @@ public int findDuplicate(int[] nums) {
         }
         return left;
     }
+}
+
+
+/*
+位运算：将 原数组 与 [1,n]数字 转化成二进制后，统计对应每一位1的个数，原数组比范围数组 位上多出来的1 是重复元素位上的1，找到重复元素所有位上的1后 转化得到重复元素值
+nums = [1,3,4,2,2]
+
+1 3 4 2 2 写成二进制
+ 1 [0 0 1]
+ 3 [0 1 1]
+ 4 [1 0 0]
+ 2 [0 1 0]
+ 2 [0 1 0]
+ x  1 3 2
+
+把 1 到 n，也就是 1 2 3 4 也写成二进制
+ 1 [0 0 1]
+ 2 [0 1 0]
+ 3 [0 1 1]
+ 4 [1 0 0]
+ y  1 2 2
+
+res 0 1 0
+ */
+class Solution {
+    public int findDuplicate(int[] nums) {
+        int res = 0, n = nums.length;
+        int maxBit = 31;
+        while (((n - 1) >> maxBit) == 0) {
+            maxBit--;
+        }
+        for (int i = 0; i <= maxBit; i++) {
+            int x = 0, y = 0;
+            int mask = (1 << i);
+            for (int j = 0; j < n; j++) {
+                if ((nums[j] & mask) > 0) {
+                    x++;
+                }
+                if ((j & mask) > 0) {
+                    y++;
+                }
+            }
+            if (x > y) {
+                res |= mask;
+            }
+        }
+        return res;
+    }
 }
