【LeeCode】287题：如何高效定位数组中的重复数字？

本文共计475个文字，预计阅读时间需要2分钟。

【题目描述】给定一个包含n个整数的数组nums，其中所有数字都在[1, n]范围内（包含1和n），且至少存在一个重复的整数。请找出并返回任意一个重复的整数。

假设 n 是一个整数。

给定一个包含​​n + 1​​​个整数的数组​​nums​​​，其数字都在​​[1, n]​​​范围内（包括​​1​​​和​​n​​），可知至少存在一个重复的整数。

假设​​nums​​只有一个重复的整数，返回这个重复的数。

你设计的解决方案必须不修改数组​​nums​​​且只用常量级​​O(1)​​的额外空间

​​leetcode.cn/problems/find-the-duplicate-number/?favorite=2cktkvj​​

admin

不满足题目中的只用常量级​​O(1)​​的额外空间

import java.awt.image.ImageProducer;import java.util.*;import java.util.stream.Collectors;// 2022-12-21class Solution { public int findDuplicate(int[] nums) { Map<Integer,Integer> map = new HashMap<>(); for(int x: nums){ map.put(x, map.getOrDefault(x, 0) + 1); } for (Map.Entry<Integer, Integer> entry : map.entrySet()) { if (entry.getValue() > 1){ System.out.println(entry.getKey()); return entry.getKey(); } } return -1; }}public class Main{ public static void main(String[] args) { int[] arr = {3,1,3,4,2}; int[] arr1 = {1,3,4,2,2}; new Solution().findDuplicate(arr); // 输出 3 new Solution().findDuplicate(arr1); // 输出 2 }}

​​二分法查找​​

import java.awt.image.ImageProducer;import java.util.*;import java.util.stream.Collectors;// 2022-12-21class Solution { // n+1个数字 范围是1~n public int findDuplicate(int[] nums) { int len = nums.length; if (len <= 2) return nums[0]; // Arrays.sort(nums); int left = 1; // 从1开始，到n - 1结束，共n个数字 int right = len - 1; while (left < right){ int mid = (right + left) / 2; int count = 0; for(int x: nums){ if (x <= mid){ count++; } } if (count > mid) { right = mid; }else{ left = mid + 1; } } return left; }}public class Main{ public static void main(String[] args) { int[] arr = {3,1,3,4,2}; int[] arr1 = {1,3,4,2,2}; new Solution().findDuplicate(arr); // 输出 3 new Solution().findDuplicate(arr1); // 输出 2 }}