上海建企业网站,北京高端建设网站,企业网站颜色选择,济南网站优化推广方案方法一#xff1a;遍历数组 由于只需要找出数组中任意一个重复的数字#xff0c;因此遍历数组#xff0c;遇到重复的数字即返回。为了判断一个数字是否重复遇到#xff0c;使用集合存储已经遇到的数字#xff0c;如果遇到的一个数字已经在集合中#xff0c;则当前的数字是…
方法一遍历数组 由于只需要找出数组中任意一个重复的数字因此遍历数组遇到重复的数字即返回。为了判断一个数字是否重复遇到使用集合存储已经遇到的数字如果遇到的一个数字已经在集合中则当前的数字是重复数字。 public class Solution {public int FindRepeatNumber(int[] nums) {HashSetint map new HashSetint();for(int i 0; i nums.Length; i){if(map.Contains(nums[i]))return nums[i];elsemap.Add(nums[i]);}return -1;}
}方法二类似交换排序 由于题目规定所有数字都在 0n-1 的范围内因此如果没有任何重复数字数组从小到大排列后是下标为i的位置对应数字i。
可以判断i与数组中下标i位置的数字m是否相等如果不相等将下标i位置的数字m交换到数组中下标为m的位置。思想其实就是不断的遍历将无序的数组逐渐变成有序如果中间遇到下标位置下标i位置的数字m与下标为m的位置数字相等则得到最终结果。
时间复杂度O(nlogn) 最坏情况下的排序
空间复杂度O(1)
public class Solution {public int FindRepeatNumber(int[] nums) {for(int i 0; i nums.Length; i){if(i ! nums[i]){if(nums[nums[i]] ! nums[i])nums[nums[i]] nums[i];elsereturn nums[i];}}return -1;}
}
