【杂题】剑指 Offer 03. 数组中重复的数字-跟着帅地玩副业，开拓第二曲线PlayOffer

CrazyJavaBoy 永久会员 2023年3月24日上午9:13

class Solution {
    public int findRepeatNumber(int[] nums) {
        //思路：【让元素值与其下标相等】
        //时间复杂度：O(n)  空间复杂度：O(1)
        for(int i = 0; i < nums.length; i++) {
            while(nums[i] != i) {
                if(nums[nums[i]] == 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年3月14日下午7:09

根据题目特点，原地排序

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 条回复

lucca 普通 2023年1月18日上午12:30

原地变换（给每个元素找家）

时间复杂度O(N)
空间复杂度O(1)

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        // 为每个元素找家, 最终结果 nums[i] = i;
        while (i < nums.length) {
            // 找到家了, 下一位
            if (nums[i] == i) {
                i++;
                continue;
            }
            // 家里的人不是这个家该存在的人
            // 如果家里这个人, 他自己的家已经有和他相等的人, 说明他是多余的
            if (nums[i] == nums[nums[i]]) return nums[i];
            // 如果他的家里面的人和他不相等, 送他回家, 把他家的人接过来，进行下一回合
            int t = nums[i];
            nums[i] = nums[t];
            nums[t] = t;
        }
        return -1;
    }
}

0 赞同 0 条回复

努力刷题普通 2022年12月5日上午8:48

"""
Hash Table
时间: O(n)
空间: O(n)
"""
class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for i in nums:
            if i not in dic:
                dic[i] = 1
            else:
                return i

"""
检查下标
时间: O(n)
空间: O(1)
"""
class Solution(object):
    def findRepeatNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i, num in enumerate(nums):
            while nums[i] != i:
                m = nums[i]
                if nums[m] != m:
                    nums[i], nums[m] = nums[m], nums[i]
                else:
                    return m
        return -1

0 赞同 0 条回复

T 普通 2022年12月3日上午10:05

原地交换

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

0 赞同 0 条回复

派大星普通 2022年12月2日下午11:06

class Solution {
时间复杂度O(n)
    public int findRepeatNumber(int[] nums) {
        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 -1;
    }
}

0 赞同 0 条回复

青木普通 2022年12月2日上午12:02

/**
    首先想到的就是哈希
    时间O(n)
    空间O(n)
 */

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

/**
    由于是0-n之间的数，因此可以直接将数放到相应的索引处，
    如果转换的时候索引处已经有了相同数，那么就说明重复了

    时间O(n)
    空间O(1)
 */

class Solution {
    public int findRepeatNumber(int[] nums) {
        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 -1;
    }
}

0 赞同 0 条回复

訁訁訁訁訁普通 2022年12月1日上午11:05

遍历中，第一次遇到数字 x 时，将其交换至索引 x 处；而当第二次遇到数字 x 时，一定有 nums[x] = x，此时即可得到一组重复数字。

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            if (nums[i] == i) {
                i++;//占位正确
                continue;
            }
            if (nums[nums[i]] == nums[i]) return nums[i];//说明索引为nums[i]和i出现重复值
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;//交换索引为 i 和 nums[i] 的元素值，将此数字交换至对应索引位置。
            //不断重复交换总能换对
        }
        return -1;
    }
}

0 赞同 0 条回复

Mooby 普通 2022年12月1日上午9:17

// 时间复杂度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 tmp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = tmp;
            }
        }
        return -1;
    }
}

0 赞同 0 条回复

西西弗斯的石头永久会员 2022年11月30日下午8:56

时间复杂度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]]){
                int temp = nums[nums[i]];
                nums[nums[i]] = nums[i];
                nums[i] = temp;
              }else{
                return nums[i];
            }
            } 
        }
        return -1;
    }
}

0 赞同 0 条回复

🚲南下普通 2022年11月30日下午8:38

时间复杂度:O(n)
空间复杂度:O(n)
class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        map<int,int> m; //使用map存储每个数字与出现的次数
        for(auto s: nums){
            m[s]++;
        }
        for(map<int,int>::iterator it = m.begin(); it!= m.end();it++){ 
            if(it->second > 1) return it->first; //判断出现次数是否大于1
        }
        return -1;
    }
};

0 赞同 0 条回复

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

共以下 11 个回答

原地变换（给每个元素找家）

# 回答此问题取消回复

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

共以下 11 个回答

原地变换（给每个元素找家）

# 回答此问题 取消回复

# 回答此问题取消回复