【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 }}

【本文由：湖北阿里云代理 aliyun.html 复制请保留原URL】每一件事都要用多方面的角度来看它