前言
周末和大學的幾個伙計聚了一下，很開心，大家都很懂事而且都在努力，已經有兩年碩士畢業去雅虎的，薪資待遇更是沒得說，哈哈，聊得很開心，不過周末沒怎麼寫代碼，這裡在九度oj水幾道題，順便記錄一下（ps：貌似這個題目之前有記錄過，不管了）
題目
[html]
題目描述：
一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。
輸入：
輸入的第一行包括一個整數N(1<=N<=1000)。
接下來的一行包括N個整數。
輸出：
可能有多組測試數據，對於每組數據，
找出這個數組中的兩個只出現了一次的數字。
輸出的數字的順序為從小到大。
樣例輸入：
6
2 3 9 3 7 2
樣例輸出：
7 9
題目描述：
一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程序找出這兩個只出現一次的數字。
輸入：
輸入的第一行包括一個整數N(1<=N<=1000)。
接下來的一行包括N個整數。
輸出：
可能有多組測試數據，對於每組數據，
找出這個數組中的兩個只出現了一次的數字。
輸出的數字的順序為從小到大。
樣例輸入：
6
2 3 9 3 7 2
樣例輸出：
7 9
思路
這裡主要考察c的位運算，介紹兩個異或運算的性質：
任何一個數字異或它自己都等於0
任何一個數字（除0外）異或0都等於它本身
所以我們可以考慮如下思路：
從頭到尾異或數組中的每一個數字，那麼最終得到的結果就是兩個只出現一次的數字的異或結果
由於兩個數字肯定不一樣，那麼異或結果肯定不全為0,找出第一個為1的位置，記為loc
通過判斷數組每個數的loc位是否為1,將數組分為兩部分
兩部分數組分別異或即可
ac代碼
[cpp]
#include <stdio.h>
#include <stdlib.h>
int firstone_loc(int num)
{
int i;
for (i = 0; num % 2 == 0; i ++) {
num = num >> 1;
}
return i;
}
int judge_loc(int num, int loc)
{
num = num >> loc;
if (num % 2 == 1) {
return 1;
} else {
return 0;
}
}
int main(void)
{
int i, n, unique, first, second, loc, flag, *arr;
while (scanf("%d", &n) != EOF) {
arr = (int *)malloc(sizeof(int) * n);
for (i = unique = 0; i < n; i ++) {
scanf("%d", arr + i);
unique ^= arr[i];
}
// 第一個為1的位
loc = firstone_loc(unique);
for (i = first = second = 0; i < n; i ++) {
flag = judge_loc(arr[i], loc);
if (flag) {
first ^= arr[i];
} else {
second ^= arr[i];
}
}
if (first < second) {
printf("%d %d\n", first, second);
} else {
printf("%d %d\n", second, first);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1256
User: wangzhengyi
Language: C
Result: Accepted
Time:570 ms
Memory:912 kb
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
int firstone_loc(int num)
{
int i;
for (i = 0; num % 2 == 0; i ++) {
num = num >> 1;
}
return i;
}
int judge_loc(int num, int loc)
{
num = num >> loc;
if (num % 2 == 1) {
return 1;
} else {
return 0;
}
}
int main(void)
{
int i, n, unique, first, second, loc, flag, *arr;
while (scanf("%d", &n) != EOF) {
arr = (int *)malloc(sizeof(int) * n);
for (i = unique = 0; i < n; i ++) {
scanf("%d", arr + i);
unique ^= arr[i];
}
// 第一個為1的位
loc = firstone_loc(unique);
for (i = first = second = 0; i < n; i ++) {
flag = judge_loc(arr[i], loc);
if (flag) {
first ^= arr[i];
} else {
second ^= arr[i];
}
}
if (first < second) {
printf("%d %d\n", first, second);
} else {
printf("%d %d\n", second, first);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1256
User: wangzhengyi
Language: C
Result: Accepted
Time:570 ms
Memory:912 kb
****************************************************************/
這裡需要提示一下，由於我本身對位運算也不夠熟悉，因為我判斷第i位是否為1,是用%2是否為1判斷的，其實如果對位運算熟悉，直接&1即可
按照上述方法的ac代碼
[cpp]
#include <stdio.h>
#include <stdlib.h>
int firstone_loc(int num)
{
int i;
for (i = 0; (num & 1) == 0; i ++) {
num = num >> 1;
}
return i;
}
int judge_loc(int num, int loc)
{
num = num >> loc;
return (num & 1);
}
int main(void)
{
int i, n, unique, first, second, loc, flag, *arr;
while (scanf("%d", &n) != EOF) {
arr = (int *)malloc(sizeof(int) * n);
for (i = unique = 0; i < n; i ++) {
scanf("%d", arr + i);
unique ^= arr[i];
}
// 第一個為1的位
loc = firstone_loc(unique);
for (i = first = second = 0; i < n; i ++) {
flag = judge_loc(arr[i], loc);
if (flag) {
first ^= arr[i];
} else {
second ^= arr[i];
}
}
if (first < second) {
printf("%d %d\n", first, second);
} else {
printf("%d %d\n", second, first);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1256
User: wangzhengyi
Language: C
Result: Accepted
Time:560 ms
Memory:912 kb
****************************************************************/
#include <stdio.h>
#include <stdlib.h>
int firstone_loc(int num)
{
int i;
for (i = 0; (num & 1) == 0; i ++) {
num = num >> 1;
}
return i;
}
int judge_loc(int num, int loc)
{
num = num >> loc;
return (num & 1);
}
int main(void)
{
int i, n, unique, first, second, loc, flag, *arr;
while (scanf("%d", &n) != EOF) {
arr = (int *)malloc(sizeof(int) * n);
for (i = unique = 0; i < n; i ++) {
scanf("%d", arr + i);
unique ^= arr[i];
}
// 第一個為1的位
loc = firstone_loc(unique);
for (i = first = second = 0; i < n; i ++) {
flag = judge_loc(arr[i], loc);
if (flag) {
first ^= arr[i];
} else {
second ^= arr[i];
}
}
if (first < second) {
printf("%d %d\n", first, second);
} else {
printf("%d %d\n", second, first);
}
free(arr);
}
return 0;
}
/**************************************************************
Problem: 1256
User: wangzhengyi
Language: C
Result: Accepted
Time:560 ms
Memory:912 kb
****************************************************************/
對比
大家可以看到，明顯位運算要比取余運算快10ms的時間
