leetcode 287. Find the Duplicate Number 三种解法

题意

int[n + 1] 的数组里存着[1,n]的数字，找出重复我唯一数字。

testcase

[1,3,4,2,2] [3,1,3,4,2] [2,2,2,2,2] [1,1] [1,1,2]

一开始以为存了1到n，多一个不知道什么数，求出它就行了。所以我用求和1到n，然后遍历减去，最后乘以-1，结果错了，因为用例里有[2,2,2,2,2]，坑！

解1

最简单的方法全部存下来。空间复杂度O(N)。

// Runtime: 0 ms, faster than 100.00% of Java online submissions for Find the Duplicate Number. //Memory Usage: 38.7 MB, less than 13.96% of Java online submissions for Find the Duplicate Number. public int findDuplicate(int[] nums) { boolean[] visited = new boolean[nums.length]; for (int num : nums) { if (visited[num]) return num; visited[num] = true; } return 0; }

解2

排序

// Runtime: 2 ms, faster than 49.95% of Java online submissions for Find the Duplicate Number. //Memory Usage: 38.7 MB, less than 13.96% of Java online submissions for Find the Duplicate Number. public int findDuplicate(int[] nums) { Arrays.sort(nums); for (int i = 1; i < nums.length; i++) { if (nums[i - 1] == nums[i]) return nums[i]; } return 0; }

解3

龟兔赛跑。题目转换为快慢指针，同141，142题。

// Runtime: 0 ms, faster than 100.00% of Java online submissions for Find the Duplicate Number. //Memory Usage: 38.7 MB, less than 13.96% of Java online submissions for Find the Duplicate Number. public int findDuplicate(int[] nums) { int slow = 0; int fast = 0; while (true) { slow = nums[slow]; fast = nums[nums[fast]]; if (slow == fast) { int rst = 0; while (rst != slow) { rst = nums[rst]; slow = nums[slow]; } return rst; } } }