【剑指Offer】287. 寻找重复数 --- 数组求重复

这篇可以作为一个类进行归纳

数组:数组求重复

1~1000 放在 1001 长度的数组中,有一个重复值,设计算法找出。每个数组元素只能访问一次。不使用辅助空间,设计算法实现

思路 1:开辟 1000 的哈希数组,全部置 0。映射的过程中,0 置一。当重复值出现的时候,发现是 1,返回这个值

思路 2:数学法,值全部相加 sum1。1 加到 1000,sum2。最后sum1 - sum2得到就是多的。

思路 3:异或法

  • 两相同数异或为 0,否则不为 0,就不同。
  • 0 和 n 异或为 n

所以 (a[1]^ a[2]^...^a[1001]) ^(1^2^...^1000),最后剩下一堆 0 和多余的数。结果即为这个数。

思路 4:见下下题的题解

思路 5:把 a[i]对应的 k 值放到 k 位置,最后放进去的时候发现有重复的,这个值即为重复的。

思路 6:假想一个链表,查看是否有环。环入口就是重复的元素,如下题

剑指 Offer 287 - 数组重复元素 1

给定一个包含 n + 1 个整数的数组 nums,其数字都在 1 到 n 之间(包括 1 和 n),可知至少存在一个重复的整数。假设只有一个重复的整数,找出这个重复的数。可能会出现[2,2,2,2,2]

int findDuplicate(vector<int>& nums) {
        int fast = 0;
        int slow = 0;
        
        while(1){
            fast = nums[nums[fast]];
            slow = nums[slow];
            // 找到环
            if(slow == fast){
                fast = 0;// 一个指针回到起点
                while(nums[slow] != nums[fast]){
                    fast = nums[fast];
                    slow = nums[slow];
                }
                return nums[slow];
            }
        }
    }

数组:数组中重复的元素 2

给定一个整数数组 a,其中 1 ≤ a[i] ≤ nn为数组长度), 其中有些元素出现 两次 而其他元素出现 一次

找到所有出现 两次 的元素。不用到任何额外空间并在 O(n)时间复杂度内解决这个问题

思路:凡是遇到“1 ≤ a[i] ≤ n ”,即数组值范围在下标内,可考虑二者结合起来

  • 往后遍历,访问a[i],再判断a[a[i] - 1](a[i]要先绝对值处理 )
    • 大于 0,a[a[i]-1]取负
    • 小于 0,a[i]即为重复值。(值被变号过)
vector<int> findDuplicates(vector<int>& nums) 
{
    vector<int> twice = {};
    int temp = 0;
    for(int i = 0; i < nums.size()-1; i++){
            if(nums[i] > 0)
                temp = nums[i] - 1;
            else
                temp = (-1)*nums[i] - 1;
                
            if(nums[temp] < 0)
                twice.push_back(temp+1);
            else
                nums[temp] = -nums[temp];
            
        }
    return twice;
}

本文链接:https://ariser.cn/index.php/archives/379/
本站文章采用 知识共享署名4.0 国际许可协议进行许可,请在转载时注明出处及本声明!