经典算法(12) 数组中只出现1次的两个数字(百度面试题)

首先来看题目要求:

在一个数组中除两个数字只出现1次外,其它数字都出现了2次, 要求尽快找 出这两个数字。

考虑下这个题目的简化版——数组中除一个数字只出现1次外,其它数字都成对出现 ,要求尽快找出这个数字。这个题目在之前的《位操作基础篇之位操作全面总结》中的“位操作趣味应用” 中就已经给出解答了。根据异或运算的特点,直接异或一次就可以找出这个数字。

现在数组中有两个 数字只出现1次,直接异或一次只能得到这两个数字的异或结果,但光从这个结果肯定无法得到这个两个数字 。因此我们来分析下简化版中“异或”解法的关键点,这个关键点也相当明显——数组只能有一个数字出现1 次。

设题目中这两个只出现1次的数字分别为A和B,如果能将A,B分开到二个数组中,那显然符合“ 异或”解法的关键点了。因此这个题目的关键点就是将A,B分开到二个数组中。由于A,B肯定是不相等的, 因此在二进制上必定有一位是不同的。根据这一位是0还是1可以将A,B分开到A组和B组。而这个数组中其它 数字要么就属于A组,要么就属于B组。再对A组和B组分别执行“异或”解法就可以得到A,B了。而要判断A, B在哪一位上不相同,只要根据A异或B的结果就可以知道了,这个结果在二进制上为1的位都说明A,B在这一 位上是不相同的。

比如int a[] = {1, 1, 3, 5, 2, 2}

整个数组异或的结果为3^5即 0x0011 ^ 0x0101 = 0x0110

对0x0110,第1位(由低向高,从0开始)就是1。因此整个数组根据第1位是0还是 1分成两组。

a[0] =1  0x0001  第一组

a[1] =1  0x0001  第一组

a[2] =3  0x0011  第二组

a[3] =5  0x0101  第一组

a[4] =2  0x0010  第二组

a[5] =2  0x0010  第二组

第一组有{1, 1, 5},第二 组有{3, 2, 3},明显对这二组分别执行“异或”解法就可以得到5和3了。

分析至些,相信代码不难 写出,下面给出完整的源代码:

// 百度面试题
//数组中除两个数字外,其它数字都出现了次。要求尽可能快的找出这两个数字
//By MoreWindows (http://blog.csdn.net/MoreWindows)
#include <stdio.h>
void FindTwoNotRepeatNumberInArray(int *a, int n, int *pN1, int *pN2)
{
    int i, j, temp;  

    //计算这两个数的异或结果
    temp = 0;
    for (i = 0; i < n; i++)
        temp ^= a[i];  

    // 找第一个为1的位
    for (j = 0; j < sizeof(int) * 8; j++)
        if (((temp >> j) & 1) == 1)
            break;  

    // 第j位为1,说明这两个数字在第j位上是不相同的
    // 由此分组即可
    *pN1 = 0, *pN2 = 0;
    for (i = 0; i < n; i++)
        if (((a[i] >> j) & 1) == 0)
            *pN1 ^= a[i];
        else
            *pN2 ^= a[i];
}
void PrintfArray(int a[], int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", a[i]);
    putchar('\n');
}
int main()
{
    printf("    白话经典算法系列之十二数组中不重复的个数字(百度面试题) \n");
    printf(" -- by MoreWindows( http://blog.csdn.net/MoreWindows ) --\n\n");   

    const int MAXN = 10;
    //int a[MAXN] = {1, 2, 7, 5, 100,  100, 6, 1, 2, 5};
    int a[MAXN] = {1, 2, 3, 4, 1,  2, 3, 4, 0, 5};  

    printf("数组为: \n");
    PrintfArray(a, MAXN);  

    int nNotRepeatNumber1, nNotRepeatNumber2;
    FindTwoNotRepeatNumberInArray(a, MAXN, &nNotRepeatNumber1, &nNotRepeatNumber2);
    printf("两个不重复的数字分别为: %d %d\n", nNotRepeatNumber1, nNotRepeatNumber2);
    return 0;
}

运行结果如下所示:

百度面试在算法这一环节上一 般会出多道算法题,下次再整理几篇,欢迎大家继续参阅。

原文地址: http://blog.csdn.net/morewindows/article/details/8214003

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索数组
, int
, 异或
, 数字
, pn532
, 结果
, 数组中未出现的数字
, 两个
, 解法
, 经典面试题
, 数字数组
两个数字
经典算法面试题、java经典算法面试题、经典算法面试题及答案、数字图像处理经典算法、算法面试题,以便于您获取更多的相关知识。

时间: 2024-02-19 20:16:18

经典算法(12) 数组中只出现1次的两个数字(百度面试题)的相关文章

如何数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 输入 每个测试案例包括两行 第一行包含一个整数n,表示数组大小.2<=n <= 10^6. 第二行包含n个整数,表示数组元素,元素均为int. 输出 对应每个测试案例,输出数组中只出现一次的两个数.输出的数字从小到大的顺序. 样例输入: 8 2 4 3 6 3 2 5 5 样例输出: 4 6 思路:上篇博文中已经了解到异或去重的原理,而且知道如果只有一个只出现一次的数字的求法,但这里是有两个

JavaScript使用二分查找算法在数组中查找数据的方法_javascript技巧

本文实例讲述了JavaScript使用二分查找算法在数组中查找数据的方法.分享给大家供大家参考.具体分析如下: 二分查找又称折半查找,优点是比较次数少,查找速度快,平均性能好:其缺点是要求待查表为有序表,且插入删除困难.因此,折半查找方法适用于不经常变动而查找频繁的有序列表.首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功:否则利用中间位置记录将表分成前.后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一

[剑指Offer]40.数组中只出现一次的数字

题目 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 思路 我们直到异或的性质: 任何一个数字异或他自己都等于0. 所以说我们如果从头到尾依次异或每一个数字,那么最终的结果刚好只出现一次的数字,因为成对出现的两次的数字全部在异或中抵消了. 这道题中有两个数字只出现一次.这样的话我们得到的结果就是这两个数字的异或结果.因此我们想办法把原数组分成两个子数组,使得每个子数组包含一个只出现一次的数字.这样我们就可以对这两个子数组分别异或,就能得到两个只出现一

在O(n)时间复杂度O(1)空间复杂度求一个数组中出现多次和未出现的数字

问题描述 在O(n)时间复杂度O(1)空间复杂度求一个数组中出现多次和未出现的数字 爱奇艺笔试题: 原题是:已知一个数组A[],大小为N,其中每个数都为1-N,请求出该数组中未出现的数字和出现多次的数字. 要求是时间复杂度为O(N),空间复杂度为O(1) 这道题的关键点就在于空间复杂度为O(1),本来想到的2-bitmap因为这点也不能实现了. 提示是:要善于利用%操作符 void appears(int r[], int n) { int i; for (i = 0; i < n; ++i)

Linux中/etc/fstab配置项里最后两个数字是什么意思?

Linux中/etc/fstab配置项里最后两个数字是什么意思? 我们先来看一下这个/etc/fstab的文件内容: [root@localhost&http://www.aliyun.com/zixun/aggregation/37954.html">nbsp;software]# vi /etc/fstab     #  # /etc/fstab  # Created by anaconda on Sat Jun  8 16:22:16 2013  #  # Accessibl

求数组中只出现一次的数字的算法

题目: 一个整型数组里除了两个数字以外, 其他的数字都出现了两次. 请写程序找出这两个只出现一次的数字. 如果从头到尾依次异或数组中的每一个数字, 那么最终的结果刚好是那个只出现一次的数字. 根据结果数组二进制某一位为1, 以此分组, 为1的一组, 为0的一组, 再重新进行异或. 最后得出两个结果. 时间复杂度O(n). 代码: /* * main.cpp * * Created on: 2014.6.12 * Author: Spike */ /*eclipse cdt, gcc 4.8.1*

求数组中只出现一次的数字(算法)

首先,我们先考虑简单的情况下,就是只有一个出现一次的数字,其余数字都出现2次,这样我们可以采用一种很巧妙的方法:"异或". void findNumAppearOnce(int date[],int length,int &num) { if(length<2) return; num=0; for(int i=0;i<length;i++) { num ^=date[i]; } } 然后,我们考虑有两个出现一次的数字的情况.同理,我们依然采用上面的方法,由于两个出

【3】数组中只出现一次的数字

题目:输入一个整型数组,数组里除了两个数出现一次之外,其它所有数字出现的次数都是2次,求这两个数字.要求时间复杂度为O(n),空间复杂度为O(1) 1 题目要求时间复杂度为O(n)并且空间复杂度为O(1).这个时候朴素的方法利用数字来记录出现次数的方案都是不行的. 2 根据题目的特点,只有两个数出现一次,其它的所有数据都是出现2次.如果这两个数是a和b,那么对这个数组异或的结果就是a^b.现在我们就是要考虑怎么把数组分成两部分,一部分含有a,一部分含有b,则每部分异或的结果即为两个数a和b的值

剑指offer系列之三十九:数组中只出现一次的数字

题目描述 一个整型数组里除了两个数字之外,其他的数字都出现了两次.请写程序找出这两个只出现一次的数字. 先考虑只有只有一个数字出现一次的情况,因为其他数字只出现了两次,所以对这两个数字进行异或运算的时候,其结果是0,那么那个只出现一次的数字进行异或运算的时候,其结果必然不是0,所以可以利用这点找出那个只出现一次的数字.现在考虑有两个数字出现一次的情况,仍然借鉴上面的思路,因为只出现一次的那个数字的异或结果不是0,遍历整个数组进行异或运算的结果也肯定不是0,现在可以对该数右边第一个是1的位的位置作