首页分享初学C语言【14】寻找单身狗

初学C语言【14】寻找单身狗

来源：萌宠菠菠乐园时间：2024-10-12 15:51

一个数组中只有两个数字是出现一次，其他所有数字都出现了两次。编写一个函数找出这两个只出现一次的数字。LeetCode：只出现一次的数字，题目链接

示例输入：[ 1,2,3,4,5,2,1,3 ] 输出：4 , 5 方法一：先对数组进行排序，排序后进行相邻的数字比较是否相同。图示：

在这里插入图片描述

#include<stdio.h> void Bbsort(int* a,int n)//冒泡排序 { int j = 0; int i = 0; for (i = 0; i < n; i++) { for (j = 0; j < n - i - 1; j++) { if (a[j] > a[j + 1]) { int temp = a[j]; a[j] = a[j+1]; a[j + 1] = temp; } } } } void finddog(int* a, int n,int* num ) { Bbsort(a,n);//首先排序 int i = 0; int j = 0; for (i = 0; i < n;) { if (a[i] == a[i + 1])//相邻两个相等，遍历下一组 { i += 2;//跳过一组 } else//不相等，记录第一个数据，第二个为起始位置 { num[j]= a[i]; i++; j++; } } } int main() { int arr[] = { 1,2,3,4,5,2,1,3 }; int num[2] = {0}; int sz = sizeof(arr) / sizeof(arr[0]);//元素个数 finddog(arr,sz,num); printf("%d %d ", num[0],num[1]); return 0; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546' 方法二：异或（两数，相同为 0 ，相异为 1 ），整个数组全部元素进行异或，出现两次的元素异或为“0”，最后的结果不可能是零（否则没有单身狗了，不可能，我就是单身狗），寻找数组元素异或后二进制为 1 的位置（区别），然后将该数组分为两组，一组该二进制位全为 1 ，将数组中该位为1的所有数异或，因为数组中相同的数异或为0，仅留下该位为1的单身狗数；另外一组该位全为0，同理，该位为0的所有数异或，最后仅留下该位为0的单身狗数。

#include<stdio.h> void finddog(int a[], int sz, int* num) { int i = 0; int pos = 0; int ret = 0; //遍历数组，结果为两个不同数的异或。 for (i = 0; i < sz; i++) { ret ^= a[i]; } //寻找这两个不同数异或结果的一个位为 1 的位 for (pos = 0; pos < 32; pos++) { if (((ret >> pos) & 1) == 1)//整型 32 位，从低位向高位依次遍历 { break; //pos记录二进制位为 1 的数 } } for (i = 0; i < sz; i++) { //找到数组中pos位为1的数，并进行异或 if (((a[i] >> pos) & 1) == 1) { num[1] ^= a[i]; } //找到数组中pos位为0的数，并进行异或 else { num[0] ^= a[i]; } } } int main() { int arr[] = { 1, 2, 3, 4, 5, 2, 1, 3 }; int num[2] = { 0 }; int sz = sizeof(arr) / sizeof(arr[0]); finddog(arr, sz, num); printf("%d %dn", num[0], num[1]); return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142'

网址: 初学C语言【14】寻找单身狗 https://www.mcbbbk.com/newsview369496.html

所属分类：萌宠日常