给定一个包含 n 个正整数的数组 nums,数组中所有数字都在区间 [1,n-1] 内,但有一个数出现了两次及以上,其余所有数字都仅出现一次。
例如 [4,2,3,1,4] ,其中 4 出现了两次。
例如 [4,2,3,1,4] ,其中 4 出现了两次。
请你找到这个重复的数。
进阶一:
请你找到一个时间复杂度为,空间复杂度为的方法
进阶二:
请你找到一个时间复杂度为,空间复杂度为的方法
数据范围:
[4,2,1,3,3]
3
[1,2,3,4,5,6,7,8,9,9]
9
import java.util.*; public class Solution { public int findRepeatNum (ArrayList<Integer> nums) { int n = nums.size(); for (int i = 0; i < n; i++) { int cur = Math.abs(nums.get(i)); if (nums.get(cur) < 0) return cur; nums.set(cur, 0 - nums.get(cur)); } return -1; } }
class Solution { public: /** */ int findRepeatNum(vector<int>& nums) { int i = 0; for (; i < nums.size(); i++) { if (nums[abs(nums[i]) - 1] > 0) { nums[abs(nums[i]) - 1] *= -1; } else { break; } } return abs(nums[i]); } };
function findRepeatNum( nums ) { // 找环入口 let slow = 0, fast = 0; do{ //快指针走两步,慢指针走一步 slow = nums[slow]; fast = nums[nums[fast]]; }while(slow != fast); slow=0; while(nums[slow] !== nums[fast]){ fast = nums[fast]; slow = nums[slow]; } return nums[slow]; } module.exports = { findRepeatNum : findRepeatNum };
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @return int整型 */ int findRepeatNum(vector<int>& nums) { // write code here int slow=0,fast=0; slow=nums[slow]; fast=nums[nums[fast]]; while(slow!=fast){ slow=nums[slow]; fast=nums[nums[fast]]; } slow=0; while(slow!=fast){ slow=nums[slow]; fast=nums[fast]; } return slow; } };
// 利用符号 原地哈希 import java.util.*; public class Solution { // 原地哈希 public int findRepeatNum (ArrayList<Integer> nums) { for (int i = 0; i < nums.size(); i++) { int idx = Math.abs(nums.get(i)); if (nums.get(idx) > 0) { nums.set(idx, nums.get(idx)*-1); } else { return idx; } } return -1; } }