力扣442数组中重复的数据：六种实现方案，暴力线性查找，排序+二分查找，排序+双指针，哈希查找，标记数组，复用 nums 成为标记数组

秒速五厘米 2024-04-22 05:43 3阅读 0赞

#### 文章目录 ####

*  第一部分：题目描述
 *  第二部分：代码实现
 *   *  2.1 方法一：暴力线性查找
     *  2.2 方法二：排序+二分查找
     *  2.3 方法三：排序+双指针
     *  2.4 方法四：哈希查找
     *  2.5 方法五：标记数组
     *  2.2 方法六：复用 nums 成为标记数组

## 第一部分：题目描述 ##

🏠 链接：[442. 数组中重复的数据 - 力扣（LeetCode）][442. _ - _LeetCode]

⭐ 难度：中等

![image-20240413140545706][]

## 第二部分：代码实现 ##

### 2.1 方法一：暴力线性查找 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for (int i = 0; i < nums.length - 1; i++) {
        
                for (int j = i + 1; j < nums.length; j++) {
        
                    if (nums[i] == nums[j]) {
        
                        list.add(nums[i]);
                        break;
                    }
                }
            }
    
            return list;
        }
    }

### 2.2 方法二：排序+二分查找 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            ArrayList<Integer> list = new ArrayList<>();
            Arrays.sort(nums);
            for (int i = 0; i < nums.length - 1; i++) {
        
                if (binarySearch(i + 1, nums.length - 1, nums, nums[i])) {
        
                    list.add(nums[i]);
                }
            }
    
            return list;
        }
    
        private boolean binarySearch(int left, int right, int[] nums, int targetVal) {
        
            while (left <= right) {
        
                int mid = (left + right) >>> 1;
                if (targetVal < nums[mid]) {
        
                    right = mid - 1;
                } else if (nums[mid] < targetVal) {
        
                    left = mid + 1;
                } else {
        
                    return true;
                }
            }
    
            return false;
        }
    }

### 2.3 方法三：排序+双指针 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            ArrayList<Integer> list = new ArrayList<>();
            Arrays.sort(nums);
            int i = 0;
            while (i < nums.length - 1) {
        
                if (nums[i] == nums[i + 1]) {
        
                    list.add(nums[i]);
                    i = i + 2;
                } else {
        
                    i++;
                }
            }
    
            return list;
        }
    }

### 2.4 方法四：哈希查找 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            Map<Integer, Integer> map = new HashMap<>();
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums) {
        
                int count = map.getOrDefault(num, 0) + 1;
                if (count == 1) {
        
                    map.put(num, count);
                } else {
        
                    list.add(num);
                }
            }
    
            return list;
        }
    }

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            HashSet<Integer> set = new HashSet<>();
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums) {
        
                // 加入失败，说明之前存在，重复了，就加入 list
                if (!set.add(num)) {
        
                    list.add(num);
                }
            }
            return list;
        }
    }

### 2.5 方法五：标记数组 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            boolean[] visited = new boolean[nums.length + 1];
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums) {
        
                // 如果已经加入过了，说明重复
                if (visited[num]) {
        
                    list.add(num);
                } else {
        
                    visited[num] = true;
                }
            }
            return list;
        }
    }

### 2.2 方法六：复用 nums 成为标记数组 ###

class Solution {
        
        public List<Integer> findDuplicates(int[] nums) {
        
            ArrayList<Integer> list = new ArrayList<>();
            for (int num : nums) {
        
                int n = Math.abs(num) - 1;
                if (nums[n] < 0) {
        
                    list.add(n + 1);
                } else {
        
                    nums[n] = -nums[n];
                }
            }
    
            return list;
        }
    }

[442. _ - _LeetCode]: https://leetcode.cn/problems/find-all-duplicates-in-an-array/description/
[image-20240413140545706]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/d8c32e96f0f346fd932a1b59347e0010.png