【杂题】剑指 Offer 03. 数组中重复的数字

本问题对应课程链接：剑指offer刷题第三期

要求：
1、请打卡你的解题代码，如果能简单说一下思路则简单说一下思路。
2、给出你代码所用的时间复杂度和空间复杂度

shuaidi

更新于 3 年前 89 9

共以下 9 个回答

九号球普通 2023年12月3日下午10:39

“`java
class Solution {
public int findRepeatDocument(int[] documents) {
if (documents == null || documents.length == 0) {
return 0;
}
//优化，不使用额外空间，因为数组中的元素小于等于数组的长度，所以可以把数组元素放到对应下标上
for (int i = 0; i < documents.length; i++) { while (i != documents[i]) { int h = documents[i]; if (documents[h] == h) { return h; } documents[i] = documents[h]; documents[h] = h; } } return 0; } }

0 赞同 0 条回复

登录以回复

mpweixin用户永久会员 2023年7月24日下午11:04

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            int cur = nums[i];

            if(cur != i){   //和自己的下标不对应
                //换去下标cur的位置
                if(nums[cur] == cur){   //已经存在
                    return cur;
                }else{
                    int temp = nums[cur];
                    nums[cur] = cur;
                    nums[i] = temp;
                    i--;
                }
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

张开怀普通 2023年7月24日下午8:24

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        // 遍历数组
        for(int i = 0; i < nums.size(); i++) {
            // 之所以用while，是因为交换之后，该位置的元素任然没有在正确的位置
            while(i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                // nums[i] 正确的位置在 nums[nums[i]]
                int k = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = k;
            }
        }
        return -1;
    }
};

时间复杂度：O(n)
空间复杂度：O(1)

0 赞同 0 条回复

yxy 普通 2023年7月24日下午3:16

时间O(n)

class Solution {
public:
    //最终版
    int findRepeatNumber(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;i++)
        {
            if(nums[i]<0||nums[i]>n-1)
                return -1;
        }
        for(int i=0;i<n;i++)
        {
            while(nums[i]!=i)
            {
                if(nums[nums[i]] != nums[i])
                    swap(nums[nums[i]],nums[i]);
                else
                    return nums[i];
            }
        }
        return -1;
    }
};

0 赞同 0 条回复

Vow the vow。普通 2023年7月24日上午11:43

用set去重

public int findRepeatNumber(int[] nums) {
        int n = nums.length;
        HashSet<Integer> set = new HashSet<>();
        for(int num : nums){
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;
    }

0 赞同 0 条回复

花老爷普通 2023年7月23日下午5:58

排序
时间：O(nlogn)
空间：O(1)

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i - 1]) {
                return nums[i];
            }
        }
        return -1;
    }
}

哈希表
时间：O(n)
空间：O(n)

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            if (!set.add(num)) {
                return num;
            }
        }
        return -1;
    }
}

给出在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内这个条件时，考虑原地交换
时间：O(n)
空间：O(1)

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (i == nums[i]) {
                i++;
                continue;
            } else if (nums[nums[i]] == nums[i]) {
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[nums[i]];
            nums[temp] = temp;
        }
        return -1;
    }
}

0 赞同 0 条回复

Ming 普通 2023年7月23日下午5:16

public int findRepeatNumber(int[] nums) {
        // 遍历数组
        for(int i = 0; i < nums.length; i++) {
            // 之所以用while，是因为交换之后，该位置的元素任然没有在正确的位置
            while(i != nums[i]){
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }
                // nums[i] 正确的位置在 nums[nums[i]]
                int k = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = k;
            }
        }
        return -1;
    }

0 赞同 0 条回复

Yodl. 普通 2023年7月23日下午4:03

//哈希表
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        unordered_map<int, bool> map;
        for(int num : nums) {
            if(map[num]) return num;
            map[num] = true;
        }
        return -1;
    }
};

0 赞同 0 条回复

怀瑾永久会员 2023年7月23日下午3:59
时间复杂度O(1)
空间复杂度O(n2）

“`C++
int findRepeatNumber(int* nums, int numsSize){
if(nums == NULL || numsSize <= 0) return -1;
```
for(int i=0; i<numsSize; i++){
    for(int j=i+1; j<numsSize; j++){
        if(nums[i] == nums[j])
            return nums[i];
    }
}
return -1;
```
}

“`
0 赞同 0 条回复

登录以回复

# 回答此问题取消回复

后才能回答

【杂题】剑指 Offer 03. 数组中重复的数字

共以下 9 个回答

# 回答此问题 取消回复

# 回答此问题取消回复