HDU 2095:find your present (2) 兩種思路

HDU 2095:find your present (2)

HDU2095連結

找最優解直接看思路2

Problem Description

In the new year party, everybody will get a “special present”.Now it’s your turn to get your special present, a lot of presents now putting on the desk, and only one of them will be yours.Each present has a card number on it, and your present’s card number will be the one that different from all the others, and you can assume that only one number appear odd times.For example, there are 5 present, and their card numbers are 1, 2, 3, 2, 1.so your present will be the one with the card number of 3, because 3 is the number that different from all the others.

Input

The input file will consist of several cases.

Each case will be presented by an integer n (1<=n<1000000, and n is odd) at first. Following that, n positive integers will be given in a line, all integers will smaller than 2^31. These numbers indicate the card numbers of the presents.n = 0 ends the input.

Output

For each case, output an integer in a line, which is the card number of your present.

Sample Input

5

1 1 3 2 2

3

1 2 1

Sample Output

3

2

HintHint

use scanf to avoid Time Limit Exceeded

基本題意：多樣例輸入，輸入數字n，n一定為奇數（當n為0時停止輸入），下一行緊接着有n個數字，找出其中隻出現過一次的數字并輸出。題目保證了除了答案數字外，其他的數都是偶數個。

思路1：第一種方法比較簡單了解，也是我首次寫想到的方法，就是直接排序。因為在排序過以後，不是答案的數字的左邊或右邊（如果左右數字存在）一定能找到相等的數字，而答案數字是一定找不到的，是以當找到這種數字時，就一定是答案。

思路1代碼：

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int main()
{
    int N;
    while(cin>>N&&N)
    {
        int a[N];
        for(int i=0;i<N;++i)
            scanf("%d",&a[i]);
        sort(a,a+N);//排序
        for(int i=0;i<N;++i)
        {
            if(i-1>=0)
            {
                if(a[i]==a[i-1])
                    continue;
            }
            if(i+1<N)
            {
                if(a[i]==a[i+1])
                    continue;
            }
            cout<<a[i]<<endl;
        }
    }
}
           

思路2：這是我在評論區看到的普遍方法，也是相比于思路1運作更快的方法，更是代碼量很少的一種方法：異或。一個數字，隻要與一個數字異或過偶數次，那麼它一定會變回自己，親測有效。而一個數字與0進行異或一定還是自己。是以利用這兩個想法，隻要讓一個變量初始化為0，然後與所有輸入的數字進行異或，然後這個變量一定會異或到答案，然而答案與其他數字進行偶數次異或之後還是答案本身，是以異或完所有的輸入以後，這個變量最終結果就是答案。

思路2代碼（想到寫起來就太快了）：

#include<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    while(cin>>n&&n)
    {
        int a,ans=0;
        for(int i=0;i<n;++i)
        {
            scanf("%d",&a);
            ans^=a;
        }
        cout<<ans<<endl;
    }
}