亲宝软件园·资讯

展开

C语言计算连续无序数组中缺省数字方法详解

36°熨斗的焦虑日记 人气:0

求缺省数字时可以使用异或进行求解,时间复杂度为O(N)。

我们都知道,异或的特点就是相同为0,相异为1 ,比如:

这是3和3相异或的结果,为0, 同样地,有4^4 = 0,5^5 = 0等等……

这也是我们思考这道题的出发点:

既然相同异或就为0,那么我们是不是只要将此数组与一个完整数组(个人习惯称为完全数组)挨个求异或,相同的数字就会被异或没,剩下的那个数字(这个数字是在完全数组中留下的)是不是就是题给数组的缺省数字?

答案是肯定的:

此时剩下的数字就是4即为所求。

但是我们怎么样用代码去实现呢?

本质上是两两求异或,非要两个数组的数字对应相异或吗?(1-1,2-2,3-3,5-5,6-6,7-7)

我们可以很快的实现一个完全数组的创建,找到缺省数组的最小值,往后加(N+1)个数便可得到,但是如果题给的数组是乱序呢?我们无法做到一一对应去求异或。

于是,奇妙的异或运算便替我们省去了很多步骤。

异或运算是有交换律的,即:a⊕b = b⊕a;

难理解的话我们来看一个例子:

假如现在有一个数组:{1,2,1,3,4};其中有两个 1 重复了,我已如果对这个数组进行两两异或结果是不是应该为2^3^4的值呢?

很显然,异或消去相同数并不需要对应,只要让这个数字最终和一个跟它相同的数字异或就可以消去;所以,我们可以将完全数组与缺省数组混合起来成为一个数组两两异或,就可以求出那个缺省数字。

思想就是这个样子,但是在实现时,如果要将两个数组合并为一个数组又得有多余的步骤,所以我的做法是将两个数组各自两两异或、得到结果A和结果B;再将A与B异或得到缺省数字。

拙解

#include <stdio.h>
int fun(int arr[], int len);
int main() 
{
    int arr[] = { 78, 79, 81, 83, 82, 84 };
    int len = sizeof(arr) / sizeof(arr[0]);
    int res = fun(arr, len);
    printf("%d\n", res);
    return 0;
}
int fun(int arr[], int len)
{
    int i, j;
    int temp1 = 0, temp2 = 0;
    int min = arr[0];
    //确定完全数组起始值
    for (i = 0; i < len; i++)
    {
        if (arr[i] < min)
        {
            min = arr[i];
        }
    }
    //对完全数组进行异或
    for (j = min; j < (len + 1)+min; j++)
    {
        temp1 ^= j;
    }
    //对原始(缺数)数组进行异或
    for (i = 0; i < len; i++)
    {
        temp2 ^= arr[i];
    }
    int res = temp1 ^ temp2;
    return res;
}

加载全部内容

相关教程
猜你喜欢
用户评论