物业服务网站建设,佛山做网站公司有哪些,如何做好网站建设工作,宁夏网站建设价格题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0#xff5e;n-1 的范围内。数组中某些数字是重复的#xff0c;但不知道有几个数字重复了#xff0c;也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1#xff1a; …题目描述
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0n-1 的范围内。数组中某些数字是重复的但不知道有几个数字重复了也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1
输入
[2, 3, 1, 0, 2, 5, 3]
输出2 或 3限制 2 n 100000 2 n 100000 2n100000 算法 1
(哈希表) O ( n ) O(n) O(n)
遍历数组判断当前数是否在哈希表中如果在则当前数就是一个重复的数直接返回否则将当前数加入到哈希表中。
时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)
C 代码
class Solution {
public:int findRepeatNumber(vectorint nums) {unordered_mapint, int hash;for (auto x : nums) {if (hash.count(x)) return x;hash[x] ;}return -1;}
};Java 代码
class Solution {public int findRepeatNumber(int[] nums) {MapInteger, Integer hash new HashMap();for (int x : nums) {if (hash.containsKey(x)) {return x;}hash.put(x, hash.getOrDefault(x, 0) 1);}return -1;}
}Python 代码
class Solution:def findRepeatNumber(self, nums: List[int]) - int:hash {}for x in nums:if x in hash:return xhash[x] hash.get(x, 0) 1return -1算法 2
(原地交换) O ( n ) O(n) O(n)
题目已知所有数的范围在 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 之间且有重复数字我们把每个数放在它的下标位置上那么对于重复数字必然会出现它的位置上已经放上了该数字。
根据以上原理遍历数组从前往后扫描每个下标 i i i 和数 n u m s [ i ] nums[i] nums[i]只要当前下标和数不对应不相等则判断下标 n u m s [ i ] nums[i] nums[i] 和这个下标上的数 n u m s [ n u m s [ i ] ] nums[nums[i]] nums[nums[i]] 是否对应如果对应则当前数就是重复数字直接返回否则交换这两个数循环此操作。
时间复杂度 O ( n ) O(n) O(n)
空间复杂度 O ( n ) O(n) O(n)
C 代码
class Solution {
public:int findRepeatNumber(vectorint nums) {for (int i 0; i nums.size(); i ) {while (nums[i] ! i nums[nums[i]] ! nums[i]) swap(nums[i], nums[nums[i]]);if (nums[i] ! i nums[nums[i]] nums[i]) return nums[i];}return -1;}
};Java 代码
class Solution {public int findRepeatNumber(int[] nums) {for (int i 0; i nums.length; i ) {while (nums[i] ! i nums[nums[i]] ! nums[i]) {int temp nums[i];nums[i] nums[temp];nums[temp] temp;}if (nums[i] ! i nums[nums[i]] nums[i]) {return nums[i];}}return -1;}
}Python 代码
class Solution:def findRepeatNumber(self, nums: List[int]) - int:for i in range(len(nums)):while nums[i] ! i and nums[nums[i]] ! nums[i]:nums[nums[i]], nums[i] nums[i], nums[nums[i]]if nums[i] ! i and nums[nums[i]] nums[i]:return nums[i]return -1推荐阅读
https://www.mianshi.online/https://www.i9code.cn/
