数据结构与算法刷题笔记——第一周2:异或运算

题目:
给定一个长度为n的整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。要求:写出线性时间复杂度的算法。
进阶:给出O(1)额外空间复杂度的算法,不考虑函数实参占用的空间。

进阶算法需要用到异或运算,由于C语言一年未用,有所生疏,特此记录。

  1. C语言中按位异或符^的作用

    0∧0=0,0∧1=1, 1^0=1,1∧1=0,一言以蔽之,“同假异真”。

  2. 实际应用
    在本题中,提供的数组只有一个元素没有相同元,而两个数进行按位异或^运算时(将数据转换为二进制数),相同的数得到的是0,我们便可利用这一特点对数组进行“筛选”,只留下所求的元素。具体代码如下。

#include <stdio.h>
#include <stdlib.h>
#define N 5

int find_alone(int nums[], int n) ;

int main()
{
    int n,i;
    int nums[N];
    int temp;
    for(i = 0;i<5;i++)//此处会略过回车(字符)、空格
    {
        scanf("%d",&nums[i]);
    }
    scanf("%d",&n);
    temp = find_alone(nums,n);
    printf("%d",temp);
    return 0;
}

int find_alone(int nums[], int n) //异或
{
    int temp = 0;
    int i;
    for(i = 0;i < n;++i)
    {
        temp^=nums[i];
    }
    return temp;
}
上一篇:分布式锁


下一篇:dotnet 里的那些锁 AutoResetEvent 用法