leetcode 442. Find All Duplicates in an Array | 442. 数组中重复的数据（位运算）

淩亂°似流年 2022-09-04 07:56 149阅读 0赞

## 题目 ##

[https://leetcode.com/problems/find-all-duplicates-in-an-array/][https_leetcode.com_problems_find-all-duplicates-in-an-array]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]

## 题解 ##

没想出来，看了评论之后写的，一语点醒。

思路就是，用num对应index的最高位表示是否出现过。

class Solution { 
        public List<Integer> findDuplicates(int[] nums) { 
            // when find a number i, flip the number at position i-1 to negative.
            // if the number at position i-1 is already negative, i is the number that occurs twice.
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length; i++) { 
                int n = nums[i] & (0b01111111_11111111_11111111_11111111); // 最高位置0
                if (nums[n - 1] >>> 31 == 1) list.add(n);
                else nums[n - 1] |= (1 << 31);
            }
            return list;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]

[https_leetcode.com_problems_find-all-duplicates-in-an-array]: https://leetcode.com/problems/find-all-duplicates-in-an-array/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70]: /images/20220829/0e9922dfb9ed452880f2ac89f8cb7c28.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NpbmF0XzQyNDgzMzQx_size_16_color_FFFFFF_t_70 1]: /images/20220829/43fc6edcd9474855aedfbd7c02aca047.png