题目:
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1:
输入:
[2, 3, 1, 0, 2, 5, 3]
输出:2 或 3
限制:
2 <= n <= 100000
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
方法一:哈希表
1 class Solution { 2 public int findRepeatNumber(int[] nums) { 3 HashMap<Integer, Integer> map = new HashMap<>(); 4 for (int num : nums){ 5 map.put(num, map.getOrDefault(num, 0) + 1); 6 } 7 for (int num : map.keySet()){ 8 if (map.get(num) >= 2) return num; 9 } 10 return -1; 11 } 12 }
方法二:原地交换
利用题目已知条件:长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。表示出现的每个数字都可以找到每个索引。
看了K神评论区的老师解释:
”
原地交换法就相当于分配工作,每个索引代表一个工作岗位,每个岗位必须专业对口,既0索引必须0元素才能上岗。而我们的目的就是找出溢出的人才,既0索引岗位有多个0元素竞争。
我们先从0索引岗位开始遍历,首先我们看0索引是不是已经专业对口了,如果已经专业对口既nums[0]=0,那我们就跳过0岗位看1岗位。如果0索引没有专业对口,那么我们看现在0索引上的人才调整到他对应的岗位上,比如num[0]=2,那我们就把2这个元素挪到他对应的岗位上既num[2],这个时候有两种情况:1、num[2]岗位上已经有专业对口的人才了,既num[2]=2,这就说明刚刚那个在num[0]上的2是溢出的人才,我们直接将其返回即可。2、num[2]上的不是专业对口的人才,那我们将num[0]上的元素和num[2]上的元素交换,这样num[2]就找到专业对口的人才了。之后重复这个过程直到帮num[0]找到专业对口的人才,然后以此类推帮num[1]找人才、帮num[2]找人才,直到找到溢出的人才。
“
算法思路:
从下标为0开始遍历数组nums,正常应该是nums[i] = i,如果下标为 i 的数字不是 i 的话,假设为temp,就将nums[temp] 与nums[i]进行交换。在交换的过程中,如果遇到重复数字,就将nums[i]进行返回即可。遍历完也没有返回值,直接返回-1。
1 class Solution { 2 public int findRepeatNumber(int[] nums) { 3 for (int i = 0; i < nums.length; i++){ 4 while(nums[i] != i){ 5 if (nums[nums[i]] == nums[i]){ 6 return nums[i]; 7 } 8 int temp = nums[i]; 9 nums[i] = nums[temp]; 10 nums[temp] = temp; 11 } 12 } 13 return -1; 14 } 15 }
标签:Java,offer03,nums,int,索引,num,数组,专业对口,数字 From: https://www.cnblogs.com/liu-myu/p/17295750.html