验证中...
Solution.java
Raw Copy
public class Solution {
public int findDuplicate(int[] nums) {
int len = nums.length;
for (int i = 0; i < len; i++) {
while (nums[i] != i + 1) {
if (nums[i] == nums[nums[i] - 1]) {
return nums[i];
}
swap(nums, i, nums[i] - 1);
}
}
// 数组中没有重复的整数,测试用例错误
return 0;
}
private void swap(int[] nums, int index1, int index2) {
if (index1 == index2) {
return;
}
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
0287-寻找重复数(桶排序).py
Raw Copy
from typing import List
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# 桶排序,数字 i 应该在索引 i - 1 上,否则交换
size = len(nums)
for i in range(size):
while nums[i] != i + 1:
if nums[i] == nums[nums[i] - 1]:
return nums[i]
self.__swap(nums, i, nums[i] - 1)
def __swap(self, nums, index1, index2):
if index1 == index2:
return
nums[index1], nums[index2] = nums[index2], nums[index1]

Comment list( 1 )

426516_weimingge
liweiwei1419 2019-07-12 09:28

桶排序的思想是“一个萝卜一个坑”。对于这道题而言,遇到两个萝卜一个坑的,返回那个“萝卜”就好了。以数组 [1, 3, 4, 2, 2] 为例。

LeetCode 第 287 题:寻找重复数

这里数与要放置的位置的索引有一个偏差,编码的时候要注意这一点。再整理一下思路:如果数字 i 没有放在索引 i - 1 上,就要执行交换,把数字 i 放在索引 i - 1 上,如果索引 i - 1 上的那个元素恰好和自己相等,就没有必要交换,说明出现重复了,即找到了这个重复的元素,返回即可

解释一下编码的细节,可能有些朋友会比较晕。

1、nums[i] != i + 1:想一想正确放置的情况,nums[0] = 1nums[1] = 2,依次类推,这一步是在判断,在遍历的时候,当前索引上的放置的元素的值是不是正确的“萝卜”;

2、if nums[i] == nums[nums[i] - 1]::如果不是正确的“萝卜”,就得根据当前索引上的数值,看一看这个数字应该放在哪个位置上。例如数字 4 应该放在索引 3 上,那么就要检查数字 4(这里是 nums[i]),与索引 3 (这里是 nums[i] - 1)上的数值,即 nums[nums[i] - 1] 是否相等,如果相等,返回这个重复数,如果不相等,交换。

3、交换我单独写了一个方法,否则中括号会把自己绕晕。

复杂度分析

  • 时间复杂度:$O(N^2)$,这里需遍历一次整个数组,在遍历的时候还有一个 for 循环,因此时间复杂度为 $O(N^2)$。
  • 空间复杂度:$O(1)$,这里无需使用额外的辅助空间,因此空间复杂度为 $O(1)$。

You need to Sign in for post a comment

Help Search

183227_9af5e6a8_1826025 111910_4d91f001_1826025