[算法很美](位运算_1)找出数组中唯一成对的数

题目描述:找出唯一成对的数

1-1000这1000个数放在含有1001个元素的数组中,只能唯一的一个元素值重复,其他均只出现一次,每个数组元素只能访问一次,设计一个算法,将他找出来,不用辅助空间,能否设计一个算法实现。

题意:我们需要使用O(1)的空间复杂度和O(n)的时间复杂度完成这个算法,我们不妨先从暴力破解入手

暴力破解

我们可以建立一个1000个元素的数组(O(n)的空间复杂度),初始化全部赋为0,然后遍历一遍数组,利用Hash的思维,若遍历到3,则判断新开辟的数组下是否为1,若为1,则直接返回,因为这代表这个数已经出现一次,若为0,则将其赋为1.(数组从某种意义上来说是Key为正整数的Hash)

此方法空间复杂度为O(n),时间复杂度最坏情况下为O(n),代码如下所示:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    //构造数组
    int nums[11];
    for (int i = 1; i <= 10; i++)
        nums[i - 1] = i;
    nums[10] = (rand() % 10) + 1;
    int index = rand() % 10;
    int temp = nums[index];
    nums[index] = nums[10];
    nums[10] = temp;
    for (int i = 0; i < 11; i++)
        printf("%d ", nums[i]);


    
    //找重复值
    int tmp[11];//Hash
    memset(tmp, 0, sizeof(int) * 11);

    for (int i = 0; i < 11; i++)
    {
        tmp[nums[i]]++;
        if (tmp[nums[i]] == 2) {
            printf("\n重复数为:%d\n", tmp[nums[i]]);
        }
    }
    system("pause");
    return 0;

}

按位异或(抵消)

我们知道,位运算是所有云算里最快的,而异或运算有逻辑异或和按位异两种,我们来复习一下:

  • 0^1=1
  • 1^0=1
  • 0^0=0
  • 1^1=0

    • 同0异1的特性
  • 可判断奇偶、可调换元素顺序,相同两数可抵消

仔细看题,我们知道了数据范围是1到1000,只有一个数出现两次,也就是说,其999个数均为这个范围内不重复的数,只有2个数为一样的。

我们可以先算出1到1000的异或值,然后将其与有重复值的数组进行一次遍历异或,这就等于,我们让不重复的数出现了两次,而重复的数出现了三次,因为不重复的数在计算过程中无论有没有序都会依次抵消,所以在异或后所剩余的那个值就是重复值

我们将数据缩小,来做一个例子:

  • 假设是1到10个数存放在11大小空间的数组中,如下所示:

    • 1、2、3、4、5、6、6、7、8、9、10

      • 我们用肉眼可见,6为重复数值
  • 我们知道数据是1到10,则我们将这这个范围的数依次异或则为:

    • 1^2^3^4^5^6^7^8^9^10
    • 得到结果为11
  • 我们用11再去遍历上面那个数组依次做异或

    • 11^1^2^3^4^5^6^6^7^8^9^10
    • 得到结果就为6

这儿可能会有疑惑,为什么会这样?我们反过来看,是否可虚拟的将第一次计算与第二次计算实质化一下:

  • 1^2^3^4^5^6^7^8^9^10^1^2^3^4^5^6^6^7^8^9^10

    • 标红的为第一次所计算的
    • 我们可以发现,除了6出现了三次其余两数出现了两次
    • 那么出现两次的数将会在运算过程中抵消,得到最后的结果即是6、
    • 而我们知道数据的范围,则可不使用多余的空间将第一次的内容计算出来

代码如下所示:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int main()
{
    //构造数组
    int nums[1001];
    for (int i = 1; i <= 1000; i++)
        nums[i - 1] = i;
    nums[1000] = (rand() % 1000) + 1;
    int index = rand() % 1000;
    int temp = nums[index];
    nums[index] = nums[1000];
    nums[1000] = temp;
    for (int i = 0; i < 1001; i++)
        printf("%d ", nums[i]);



    //找重复值
    int res = 0;
    for (int i = 1; i <= 1000; i++) res ^= i;
    for (int i = 0; i < 1001; i++) res ^= nums[i];
    printf("\n重复值为:%d\n", res);
    system("pause");
    return 0;

}

相减抵消

若对上一种解法还有疑惑,这里还有种易懂的解法,能跟好的助于理解上一种的原理,

我们知道数据范围,就将这个范围内的数相加起来,然后原数组,将元素累加,最后减去这个范围内的数,就是重复的数

因为:

  • 已知数据范围
  • 已知只有一个数重复出现一次

我们可以缩小规模做一个简单的例子

  • 1、2、3、3、4、5、6、7、8、9、10,sum=58
  • 1、2、3、4、5、6、7、8、9、10,sum=55
  • 相减正好为3

这原理与上述的位运算可以视作一个道理。

教学视频如下所示:

点击进入

利用高位存储

这里提供一种思路,由大佬所讲述,因为我们知道数据范围,每个整型占16位,而我们给定的数据最大不会超过低10位,我们可屏蔽最高位用最高位做一个判断,若出现一次,则为01,若出现两次,则为10,利用第一种的过程也可解决这个问题,奈何自己愚笨,并不能实现,若有大佬能实现这种解法,麻烦评论或者联系,万分感谢!

本文链接:

https://nullcode.fun/99.html
1 + 8 =
快来做第一个评论的人吧~