【作业4】下标法：剑指 Offer 03. 数组中重复的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

超人阿光永久会员 2024年7月25日下午5:12

class Solution {
public int findRepeatDocument(int[] documents) {
if(documents null || documents.length 0) return -1;

    // 数组计数法或者数组下标法
    /*
    范围为：0 ~ 99999；
    类型为int
     */

    int[] count = new int[100001];

    // 遍历目标数组
    for(int i = 0; i < documents.length; i++){
        count[documents[i]]++;
    }

    // 返回统计数组中任一 >= 2 的项
    for(int i = 0; i < count.length ; i++){
        if(count[i] >= 2) return i;
    }

    // 没有则返回-1；
    return -1;
}

}

0 赞同 0 条回复

幽小皮永久会员 2024年3月30日下午7:19

`//代码
class Solution {
public int findRepeatDocument(int[] documents) {
int temp = 0;
for (int i = 0; i < documents.length; i++) {
while (documents[i] != i) {
if(documents[documents[i]] documents[i]){
return documents[i];
}
temp = documents[documents[i]];
documents[documents[i]] = documents[i];
documents[i] = temp;
}
}
return 0;
}
}“java

0 赞同 0 条回复

开心果🍅 永久会员 2024年3月28日下午9:34

打卡

“`java
class Solution {
public int findRepeatDocument(int[] documents) {
for (int i = 0; i

0 赞同 0 条回复

Thaddeus 永久会员 2023年8月28日下午2:49

打卡

/*
下标法
通过不断交换元素，使得元素和其下标相等，一旦以该元素为下标的位置的元素==该元素了，说明重复了
*/
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){
            while(nums[i] != i){
                if(nums[i] == nums[nums[i]]) return nums[i];
                int tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }
        return -1;
    }
};

0 赞同 0 条回复

泡芙永久会员 2023年8月25日上午11:00

它考察的是程序员的沟通能力，先问面试官要时间/空间需求！！！

最优解：下标法

Time：O(n)，因为每次交换的时候都会让一个元素回到正确的位置上，最多只会交换n次

Space：O(1)

下标法：通过不停交换元素，使得元素和它所对应的下标相等，即num[i] = i

nums[i] nums[nums[i]]

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; i ++) {
            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;
    }
}

排序法：

调用JDK中的任一排序函数进行排序，然后遍历数组，让i和i+1进行比较，重复就返回

下标： 0 1 2 3 4

元素： 2 0 1 2 3

排序： 0 1 2 2 3

        i  i+1

          i  i+1

            i  i+1    此时相等，就return i

Time：O(nlogn)，主要是排序函数需要nlogn

Space：O(1)

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

哈希表：

new一个Hash表，然后遍历元素，判断一下这个元素是否在Hash表中，如果不存在就把它放进来，如果存在的话，说明重复了，直接返回

Time：O(n)，遍历数组使用 O(n) ，HashSet 添加与查找元素皆为 O(1)

Space：O(n)，HashSet 占用 O(n)大小的额外空间。

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

1 赞同 0 条回复

阿尚普通 2023年8月16日上午11:47

class Solution {
    public int findRepeatNumber(int[] nums) {

        int res = -1;
        int i = 0;

        while(i < nums.length){
            if(i == nums[i]){
                i++;
                continue;
            }
            //如果有重复的数的话，就会出现有两个元素 a 对应到同一个 arr[a] 上，也就是出现了重复。
            if(nums[i] == nums[nums[i]]){
                res = nums[i];
                break;
            }else{
                int temp = nums[i];
                nums[i] = nums[temp];
                nums[temp] = temp;
            }
        }

        return res;
    }
}

0 赞同 0 条回复

𬍤永久会员 2023年7月26日下午1:16

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

    for(int i = 0; i < nums.length; i++){
        if(s[nums[i]] > 1){    //判断
            return nums[i];    //输出
        }
    }
    return -1;
}

}

0 赞同 0 条回复

Mr.肖永久会员 2023年7月5日下午6:36

打卡

class Solution {
    public int findRepeatNumber(int[] nums) {

        //采用数组下标法，把元素本身作为数组下标去处理一些东西
        int[] s = new int[nums.length];
        for(int i=0;i<nums.length;i++){
            s[nums[i]]++;
        }
        for(int i=0;i<nums.length;i++){
            if(s[nums[i]]>=2)
                return nums[i];
        }
        //这行代码实际上执行不到
        return -1;
    }
}

0 赞同 1 条回复

Mr.肖永久会员 @ Mr.肖 2023年7月6日上午10:16
经过一晚上，又来打卡了，这次明白了最优解的思路
题目中，数组元素的范围被限制在数组的下标中，可以利用这个条件，把元素值也考虑到数组下标中去
遍历数组，交换当前位置的元素，一直到索引值 = 元素值为止
交换元素时会发生的两种情况：
1. 得到当前位置的元素值，停止本位置的交换，进入下一个位置的交换。
2. 数组中没有当前位置的元素值，在交换过程中，两个元素被交换到某一个相同的位置，发现重复元素，返回该元素值。
代码
```
class Solution {
    public int findRepeatNumber(int[] nums) {

       //最优解思路： 元素交换 + 数组下标

       for(int i=0;i<nums.length;i++){
           while(i != nums[i]){
               if(nums[i] == nums[nums[i]])
                    return nums[i];

                 int temp = nums[nums[i]];
                 nums[nums[i]] = nums[i];
                 nums[i] = temp;
           }
       }
       return -1;
    }
}
```
登录以回复

sasuke 普通 2023年7月4日下午9:54

class Solution {
    public int findRepeatNumber(int[] nums) {
       #时间复杂度O(n) 空间复杂度O(n)
        int[] s=new int[100001];
        int num=0;
        for(int i=0;i<nums.length;i++){
            s[nums[i]]=s[nums[i]]+1;
            if( s[nums[i]]>1){
                return nums[i];
            }
        }
        return -1;

 }
}

0 赞同 0 条回复

长袜子皮皮普通 2023年7月3日上午11:03

“` java
class Solution {
public int findRepeatNumber(int[] nums) {
int[] s=new int[nums.length];
for(int i=0;ii){
i++;
continue;
}
if (nums[nums[i]]nums[i]){//下标为(索引6对应的那个数)索引6对应的数
return nums[i];
}
int temp;
temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
return 0;
}
}空间复杂度O（1）
“`

0 赞同 0 条回复

Yu 永久会员 2023年6月26日下午3:26

“`java
public int findRepeatNumber(int[] nums) {

    for (int i = 0; i < nums.length; i++) {
        //从头遍历
        //将数组中的元素 i 放到  nums[i] 的位置
        //若 i 与 nums[i] 相等 说明重复
        if (i != nums[i]) {
            if (nums[nums[i]] == nums[i]) {
                return nums[i];
            }
            else {
                int temp = nums[i];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
                i--;
            }

        }
    }

    return -1;
}

0 赞同 1 条回复

Mr.肖永久会员 @ Yu 2023年7月5日下午6:42

代码的两头都要用“
“`”包起来

登录以回复

KEV 永久会员 2023年6月3日下午9:09

c++版本

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int* count=new int[nums.size()];
        for(int i=0;i<nums.size();i++){
            count[i]=0;
        }
        // int count[nums.size()];
        // memset(count,0,sizeof(count));
        for(int i=0;i<nums.size();i++){
            count[nums[i]]++;
            if(count[nums[i]]>1){
                return nums[i];
            }
        }
        return -1;
    }
};

0 赞同 0 条回复

帅气的冬瓜普通 2023年6月2日下午5:10

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0 ;i<nums.length;i++){  
            //从第一个坑开始。
            //如果这个坑里的元素不该在这个位置，那么就把它放入它该在的坑里。
            //可能换回来的还不是这个坑里的元素，那么就继续把它放入它该在的坑里。
            //如果换坑的时候，发现那个坑里已经有属于自己的元素了。那么此元素就是重复的，返回。
            //如果第一个坑一直试到自己的元素回坑了，那么再到第二个坑里试。
            while(nums[i]!=i){  
                if(nums[nums[i]]==nums[i]){
                    return nums[i];
                }
                int temp=nums[nums[i]];
                nums[nums[i]]=nums[i];
                nums[i]=temp;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

李郎萍普通 2023年5月23日上午12:23

class Solution {
    public int findRepeatNumber(int[] nums) {
        //遍历数组
        for(int i = 0;i < nums.length;i++){
           //索引i的值为i,无需交换，继续查看下一位
            if(nums[i] == i){
                continue;
            }else{
               //索引 nums[i] 处的值也为 nums[i]，即找到一组相同值，返回 nums[i] 即可
                if(nums[nums[i]] == nums[i]) return nums[i];
              //执行交换操作，目的是为了使索引与值一一对应，即索引 0 的值为 0，索引 1 的值为 1
                int tmp = nums[i];
                nums[i] = nums[tmp];
                nums[tmp] = tmp;
                i--;
            }
        }
    return -1;
    }
}

0 赞同 0 条回复

mpweixin用户永久会员 2023年5月15日下午4:01

class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0;i < nums.length;i++){
            int num = nums[i];  //  取出当前元素
            if(num != i){   //当前i下标上的数不是i
                //把它调到该在的位置
                if(nums[num] == num){   //该位置已经有合适的元素说明重复
                    return num;
                }else{
                    //没重复，则交换
                    int temp = nums[num];
                    nums[num] = num;
                    nums[i] = temp;
                    i--;    //继续比较当前位置的值
                }
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

LicodeCO.LTDao 普通 2023年5月13日下午2:06

function findRepeatNumber(nums: number[]): number {
    for(let i = 0; i < nums.length; i++) {
        while(i != nums[i]) {
            // 找到重复的, 实际上重复的也就是 nums[i] nums[nums[i]]
            if (nums[i] === nums[nums[i]]) {
                return nums[i]
            }

            let temp = nums[nums[i]]
            nums[nums[i]] = nums[i]
            nums[i] = temp
        }
    }
    return -1
};

0 赞同 0 条回复

Violet 永久会员 2023年4月27日下午1:03

一

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

                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

灼华永久会员 2023年4月24日上午9:50

public static int findRepeatNumber(int[] arr) {
        for (int i = 0; i < arr.length; i++) {//最多交换n次
            while (arr[i] != i) {//如果位置和数字不匹配就进行交换,下标不等于元素
                //交换之前进行判断该位置是否已经存在一样的了
                if (arr[arr[i]] == arr[i]) {
                    return arr[i];
                }
                //arr[i] arr[arr[i]]
                int temp = arr[i];
                arr[i] = arr[temp];
                arr[temp] = temp;
            }

        }
        return -1;
    }

0 赞同 0 条回复

Only You!(^-^(^-^)) 永久会员 2023年4月17日下午7:27

public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            //数本来在对应的下标上，则跳过；
            if(nums[i] == i) {
                i++;
                continue;
            }
            //nums[i]的值 等于 以其值为下标的位置的值，则重复元素，返回
            if(nums[nums[i]] == nums[i]) return nums[i];


            //交换元素
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
    }
    return -1;
}

0 赞同 0 条回复

小趴菜永久会员 2023年4月17日上午3:59

//简单的一个下标法，只需拿一个数组记录重复出现的值作为编号，输出新的数组那个编号因为此时编号对应新数组的值大于1说明出现了两次以上
class Solution {
public int findRepeatNumber(int[] nums) {
int arr[] = new int [nums.length + 1];
for(int i = 0;i<nums.length;i++){
arr[nums[i]]++;
}
for(int j = 0;j<arr.length;j++){
if(arr[j]>1){
return j;
}
}
return -1;
}
}

0 赞同 0 条回复

小肸永久会员 2023年4月14日下午7:19

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (i == nums[i]) {
                i ++;
                continue;
            }
            if (nums[nums[i]] == nums[i]) {
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[nums[i]];
//这里是需要将nums[i]都替换成temp
            nums[temp] = temp;
        }
        return -1;
    }
}

0 赞同 0 条回复

菜心永久会员 2023年4月12日下午8:55

//时间复杂度O(n)
//空间复杂度O(1)
class Solution {
    public int findRepeatNumber(int[] nums) {
        for(int i = 0; i < nums.length; i++) {
            while(i != nums[i]) {
                if(nums[i] == nums[nums[i]]){
                    return nums[i];
                }

                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

庄重普通 2023年4月12日下午3:54

class Solution {
public:
    int findRepeatNumber(vector& nums) {

        vector tmp(nums.size(), 0);

        int ret = -1;
        for(int i = 0; i < nums.size(); i ++) {

            tmp[nums[i]] ++;
            if(tmp[nums[i]] > 1) {
                ret =  nums[i];
                break;
            }
        }

        return ret;
    }
};
// 时间复杂度O(n);
// 空间复杂度O(n);
class Solution {
public:
    int findRepeatNumber(vector& nums) {

        int ret = 0;
        for(int i = 0; i < nums.size(); i ++) {

            while(i != nums[i]){

                if(nums[nums[i]] != nums[i]) {
                    swap(nums[nums[i]], nums[i]);
                }else{
                    ret = nums[i];
                    break;
                }
            }            
        }
        return ret;
    }
};
// 时间复杂度O(n);  // 最多交换n次
// 空间复杂度O(1);
class Solution {
public:
    int findRepeatNumber(vector& nums) {

        for(int i = 0; i < nums.size(); i ++) {

            while(i != nums[i]){

                if(nums[nums[i]] != nums[i]) {
                    swap(nums[nums[i]], nums[i]);
                }else{
                    return nums[i];
                }
            }            
        }
        return -1;
    }
};
// 时间复杂度O(n);  // 最多交换n次
// 空间复杂度O(1);

0 赞同 2 条回复

shuaidi 永久会员 @ 庄重 2023年4月12日下午4:21

你这个空间复杂度是 On 吧？

登录以回复
庄重普通 @ shuaidi 2023年4月12日下午4:27

哦对，是的，习惯性打上O(1)，得注意，而且也不符合要求

登录以回复

秊永久会员 2023年4月11日下午10:44

确保 nums[i] 一定等于 i
此题交换元素的顺序，只能先赋值 nums[nums[i]] !

class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0; i < nums.length; ++i) {
            while (nums[i] != i) {  // 确保 nums[i] 一定等于 i
                if (nums[nums[i]] == nums[i]) {
                    return nums[i];
                }

                // 注意！！！
                // int tmp = nums[i];
                // nums[i] = nums[nums[i]];
                // nums[nums[i]] = tmp;
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

宁永久会员 2023年4月11日下午8:12

额外空间复杂度 O(1) 时间复杂度O(n)

class Solution {
    public int findRepeatNumber(int[] nums) {
       //原地排序
       for(int i = 0; i < nums.length; i++){
           while(i != nums[i]){
               if(nums[nums[i]] == nums[i]) return nums[i];
               //交换元素 nums[nums[i]] 和nums[i]
               int temp = nums[nums[i]];
               nums[nums[i]] = nums[i];
               nums[i] = temp;
           }
       }
       return -1;
    }
}

0 赞同 0 条回复

有去过的人普通 2023年4月11日下午7:16

下面是代码

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

0 赞同 0 条回复

是梦终空永久会员 2023年4月10日下午7:01

时间复杂度O(1)

class Solution {
    public int findRepeatNumber(int[] nums) {
        //题目中数组中数据范围为0~n-1，所以数组对应下标如果有相同数据，则为重复数字
        int i = 0;
        while(i< nums.length){
            if(nums[i] == i){      
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]){
                return nums[i];
            }
            int temp = nums[i];
            nums[i] = nums[temp];
            nums[temp] = temp;
        }
        return 0;
    }
}

0 赞同 0 条回复

Bryce 普通 2023年4月10日下午1:22

go语言解法。
时间复杂度：O(n),空间复杂度O(1)

func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); {
        n := nums[i]
        if nums[i] != i {
            if nums[i] == nums[n] {
                return n
            }
            nums[i], nums[n] = nums[n], nums[i]
        } else {
            i++
        }
    }
    return -1
}

0 赞同 0 条回复

C++小将永久会员 2023年4月9日下午7:50

作业四打卡

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        int i = 0;
        while(i < nums.size()) {
            if(nums[i] == i) {
                ++i;
                continue;
            }
            if(nums[nums[i]] != nums[i]) {
                swap(nums[nums[i]], nums[i]);
            }else{
                return nums[i];
            }
        }
        return -1;
    }
};

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

0 赞同 0 条回复

Yangon 普通 2023年4月9日下午3:50

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

双指针也可以

0 赞同 1 条回复

shuaidi 永久会员 @ Yangon 2023年4月9日下午3:57

你空间复杂度不符合要求哦，你这个额外空间复杂度是 O(n）了，要按照我要求，用下标法

登录以回复

Everglow 永久会员 2023年4月9日下午2:28

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

0 赞同 1 条回复

C++小将永久会员 @ Everglow 2023年4月9日下午7:53

兄弟，你这个可能过不了

登录以回复

mpweixin用户普通 2023年4月8日下午9:46

//

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

        for (int i = 0; i < len; i++) {
            if (s[i] > 1) return i;
        }

        return -1;
    }
}

0 赞同 3 条回复

shuaidi 永久会员 @ mpweixin用户 2023年4月8日下午10:05

你应该要去看一下题解视频，时间复杂度是可以做到O(1)，你这种方法没有真正用到下标法哦

登录以回复
mpweixin用户普通 @ shuaidi 2023年4月8日下午10:29

好的好的

登录以回复
sasuke 普通 @ shuaidi 2023年7月4日下午9:50

老师，我写的和这个差不多，这个不是使用下标法进行了统计吗，是因为时间复杂度是O（n)不是最优解是吗？

登录以回复

mpweixin用户普通 2023年4月8日下午8:50

class Solution {
    public int findRepeatNumber(int[] arr) {
         for(int i=0;i<arr.length;i++){
            while(arr[i]!=i){//如果位置和数字不匹配就进行交换
                //交换之前进行判断该位置是否已经存在一样的了
                if(arr[arr[i]]==arr[i]){
                    return arr[i];
                }
                int temp =arr[i];
                arr[i] =arr[temp];
                arr[temp]= temp;//不用temp就会被替换
            }

         }
         return -1;
    }

0 赞同 0 条回复

【作业4】下标法：剑指 Offer 03. 数组中重复的数字

共以下 33 个回答

打卡

作业四打卡

# 回答此问题取消回复

【作业4】下标法：剑指 Offer 03. 数组中重复的数字

共以下 33 个回答

打卡

作业四打卡

# 回答此问题 取消回复

# 回答此问题取消回复