1. 单身狗1
题目：
一个数组中只有一个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这一个只出现一次的数字。
例如：有数组的元素是：1，2，3，4，5，1，2，3，4，6。只有5和6只出现1次，要找出5和6。
第一种方法：暴力解题法（枚举法）
这种方法就不细致讲解了，代码就能说明方法了
#include<stdio.h> #include<stdlib.h> //第一种方法：暴力解法 //枚举法：直接用计数器的方式，找到该数字 int find_single_dog1(int arr[], int sz) { int num = 0;//作为标记，记录每位元素出现的次数 int* count = (int*)malloc(sz * sizeof(arr[0]));//记录每位元素出现的次数，然后存储起来 for (int i = 0;i < sz;i++) { for (int j = 0;j < sz;j++) { if (arr[i] == arr[j]) num++; } count[i] = num; num = 0; } for (int i = 0;i < sz;i++) { if (count[i] == 1) return arr[i]; } return -1; } int main() { int a[] = { 1,2,3,4,5,1,2,3,4 }; int n = find_single_dog1(a, 9); printf("%d", n); return 0; }
第二种方法：用异或解题
//第二种：用异或解题 int find_single_dog1(int arr[], int sz) { int n = 0; for (int i = 0;i < sz;i++) { n ^= arr[i]; } return n; } int main() { int a[] = { 1,2,3,4,5,1,2,3,4 }; int n = find_single_dog1(a, 9); printf("%d", n); return 0; }
2. 单身狗2
题目：一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。
编写一个函数找出这两个只出现一次的数字。
例如：有数组的元素是：1，2，3，4，5，1，2，3，4，6。只有5和6只出现1次，要找出5和6。
第一种方法：暴力解题法（枚举法）
这种方法就不细致讲解了，代码就能说明方法了
//第一种方法：暴力求解法 int* find_single_dog_first(int arr[], int sz) { int* find = (int*)malloc(sz * sizeof(arr[0]));//创建一个标识数组 int* re = (int*)malloc(2 * sizeof(arr[0]));//创建一个返回数组 int flag = -1;//自己也算一次，当只有自己，flag结果为0 for (int i = 0;i < sz;i++) { for (int j = 0;j < sz;j++) { if (arr[i] == arr[j]) flag++; } find[i] = flag; flag = -1; } int num = 0;//记录re的下标 for (int i = 0;i < sz;i++) { if (find[i] == 0) { re[num] = arr[i]; num++; } } return re; } int main() { int arr1[] = { 1,2,3,4,5,1,2,3,4,6}; int sz = sizeof(arr1) / sizeof(arr1[0]); int* ret = find_single_dog_first(arr1, sz); for (int i = 0;i < 2;i++) { printf("%d ", ret[i]); } return 0; }
第二种方法：用异或解题
//第二种方法：用异或的思想解题 //因为该题要返回两个int型的数据，但是函数返回只能返回一个数 //所以传入指针ps1和指针ps2来让计算后的数据能传到主函数main void find_single_dog2(int arr[], int sz, int* ps1, int* ps2) { int r = 0; //1. 全部异或在一起，找出哪个位置为一 for (int i = 0;i < sz;i++) { r ^= arr[i]; } //2. 计算出哪个位置的数字1，用&运算符 int pos = 0;//记录哪个位置为1 for (int i = 0;i < 32;i++) {//因为r是int类型，有32位 if (((r >> i) & 1) == 1) { pos = i; break; } } //3. 分组找出两个单身狗，并返回值 for (int i = 0;i < sz;i++) { if (((arr[i] >> pos) & 1) == 1) { (*ps1) ^= arr[i]; } else { (*ps2) ^= arr[i]; } } } int main() { int arr[] = { 1,2,3,4,5,1,2,3,4,6 }; int sz = sizeof(arr) / sizeof(arr[0]); int ps1 = 0; int ps2 = 0; find_single_dog2(arr, sz, &ps1, &ps2); printf("两个单身狗分别为：%d 和 %d", ps1, ps2); return 0; }
