【LeeCode】287. 寻找重复数

【题目描述】

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

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

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

​​https://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 }}