2 zxm 19960614 zxm_19960614 于 2016.03.20 20:54 提问

n个正整数构成的序列,其中有且仅有一个数在序列中出现了奇数次,其余的数均出现了偶数次。

n个正整数构成的序列,其中有且仅有一个数在序列中出现了奇数次,其余的数均出现了偶数次。找出出现了奇数次的那个数。
这题有一个解法:从头到尾将这n个数异或一遍,得到的数即为要找的那个数。
如果有且仅有两个数出现了奇数次,那该怎么算出这两个数,用这个思路

2个回答

caozhy
caozhy   Ds   Rxr 2016.03.20 21:51
zxm_19960614
zxm_19960614   2016.03.21 13:01
 #include <iostream>
using namespace std;
int main()
{
    int n;
    int *p;
    while (cin >> n)
    {
        p = new int[n];
        for (int i = 0; i < n; i++)
            cin >> p[i];
        int c = p[0];
        for (int j = 1; j < n; j++) {
            c = c^p[j];
        }
        for (int j = 0; j < n; j++) {
            for (int k = j + 1; k < n; k++) {
                if ((c ^ (p[j] ^ p[k])) == 0) {
                    if (p[j] > p[k]) 
                        cout << p[k] << ' ' << p[j] << endl;
                    else 
                        cout << p[j] << ' ' << p[k] << endl;
                    j = n;
                }
            }
        }
    }
}
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!
其他相关推荐
【算法题】找出且仅有的出现了奇数次的一个数
题目给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。解题思路关键字:异或从头到尾异或一遍,最后得到的那个数就是出现了奇数次的数。因为,两次异或同一个数,结果不变,且异或运算满足交换律。代码略
找出出现奇数次的数
http://www.cnblogs.com/biyeymyhjob/archive/2012/07/20/2601611.html 题目: 给你n个数,其中有且仅有一个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。给你n个数,其中有且仅有两个数出现了奇数次,其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那两个数。 答案:
有N个数,其中2个数出现了奇数次(这两个数不相等),其他数都出现偶数次,问用O(1)的空间复杂度,找出这两个数,不需要知道具体位置,只需要知道这两个值。
/* This finction sets the values of *x and *y to nonr-epeating elements in an array arr[] of size n*/ void get2NonRepeatingNos(int arr[], int n, int *x, int *y) { int xor = arr[0]; /* Will hold x
给出N个正整数,其中只有一个数出现了奇数次,其余的数都出现偶数次。求那个出现了奇数次的数。1<=N<=1000,N肯定是奇数。所有出现的整数都不超过1000。
给出N个正整数,其中只有一个数出现了奇数次,其余的数都出现偶数次。求那个出现了奇数次的数。1
在其它数都出现偶数次的数组中寻找出现奇数次的数
通过位运算,寻找出现出现奇数次的数
【面试题】数组中有两个元素出现了奇数次,其他元素出现了偶数次。找出这两个元素
数组中有两个元素出现了奇数次,其他元素出现了偶数次。找出这两个元素。 把原数组分为两个子数组。在每个子数组中,包含一个只出现一次的数字,而其他数字都出现两次。如果能够这样拆分原数组,按照前面的办法就是分别求出这两个只出现一次的数字了。 我们还是从头到尾依次异或数组中的每一个数字,那么最终得到的结果就是两个只出现一次的数字的异或结果。因为其他数字都出现了两次,在异或中全部抵消掉了。由于这两个数字
找出现奇数次的两个数
一个数组中,有两个数出现了奇数次,其余的数都出现偶数次,找出这两个数。 用异或操作可在O(n)时间复杂度和O(1)空间复杂度内找到。     设要找的两个数为A和B,第一步让所有的数异或,结果就是A^B ,记为C,则C中一定有不为0的二进制位,假设第k位。则A或B的第k位不为0,数组中的其余的数中若有第k位不为0的数对,则A或B与这些数对异或,可得到A或B,及异或数组中所有第k位不为0的所有数
java算法6~在其他数都出现偶数次的数组中找到出现奇数次的数
算法目的:在其他数都出现偶数次的数组中找到出现奇数次的数 算法要求:时间复杂度O(n),空间复杂度O(1) 算法思路:对于一个整数n:0^n=n      n^n=0,根据这两条规则,我们知道在这个数组中出现偶数次数的n^n=0。 实现: /* * To change this license header, choose License Headers in Project P
NKOJ-3679 找数2
P3679找数2时间限制 : 10000 MS 空间限制 : 0 KB 问题描述给你N个整数,其中有两个数字出现的次数是奇数次,其余数字都出现了偶数次,现在告诉你这n个数异或起来的结果X,请你快速找出这两个出现次数为奇数的数字。注意,此题空间复杂度要求为O(1),时间复杂度为O(n)输入格式第一行,两个整数N和X (1<=N<=1000000)第二行,N个空格间隔的整数范围是[0,100000
找数2--nkoj3679(百度面试题)
P3679  找数2 时间限制 : 10000 MS   空间限制 : 0 KB 问题描述 给你N个整数,其中有两个数字出现的次数是奇数次,其余数字都出现了偶数次,现在告诉你这n个数异或起来的结果X,请你快速找出这两个出现次数为奇数的数字。   注意,此题空间复杂度要求为O(1),时间复杂度为O(n) 输入格式 第一行,两个整数N和X (1 第二行,N个