【C语言】找单身狗

简介: 【C语言】找单身狗

找单身狗1

一个数组中只有一个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

有数组的元素是:1,2,3,4,5,1,2,3,4

只有5只出现1次,要找出5.

异或法

异或:相同为0,相异为1

比如1^2=0,2^3=0;

a^a=0;     0^a=a

异或满足交换律,如:3^4^5=3^5^4

int find_single_dog1(int arr[], int sz)
{
  int i = 0;
  int ret = 0;
  for (i = 0; i < sz; i++)
  {
    ret ^= arr[i];//ret=1^2^3^4^7^1^2^3^4=7
  }
  return ret;
}
int main()
{
  int arr[] = { 1,2,3,4,7,1,2,3,4 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int dog = find_single_dog1(arr, sz);
  printf("%d\n", dog);
  return 0;
}

找单身狗2

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

有数组的元素是:1,2,3,4,5,1,2,3,4,6

只有5和6只出现1次,要找出5和6.

思路:

将所有数组异或到一起

int i = 0;
  int ret = 0;
  for (i = 0; i < sz; i++)
  {
    ret ^= arr[i];
  }

ret=5^6=3

5的二进制表示为101

6的二进制表示为110

每一位异或得011即3

计算ret的第几位是1,

int pos = 0;
  for (i = 0; i < 32; i++)
  {
    if (((ret >> i) & 1) == 1)
    {
      pos = i;
      break;
      }
  }

计算数组中元素的第pos为1的异或

for (i = 0; i < sz; i++)
  {
    if (((arr[i] >> pos) & 1) == 1)
      {
      *dog1 ^= arr[i];
    }
  }

完整代码

#include<stdio.h>
void search_dog(int arr[], int sz,int* dog1,int* dog2)
{
  int i = 0;
  int ret = 0;
  for (i = 0; i < sz; i++)
  {
    ret ^= arr[i];
  }
  int pos = 0;
  for (i = 0; i < 32; i++)
  {
    if ((ret >> i) & 1 == 1)
    {
      pos = i;
      break;
    }
  }
  for (i = 0; i < sz; i++)
  {
    if ((arr[i] >> pos) & 1 == 1)
    {
      *dog1 ^= arr[i];
    }
  }
  *dog2 = *dog1 ^ ret;
}
int main()
{
  int arr[] = { 1,2,3,4,5,1,2,3,4,6 };
  int dog1 = 0;
  int dog2 = 0;
  int sz = sizeof(arr) / sizeof(arr[0]);
  search_dog(arr, sz, &dog1, &dog2);
  printf("%d %d", dog1, dog2);
  return 0;
}
目录
相关文章
|
6月前
|
算法 C语言
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
52 0
|
4月前
|
算法 C语言
【C语言】单身狗问题
C语言中的单身狗问题
29 1
【C语言】单身狗问题
|
5月前
|
C语言
C语言---单身狗(1)---在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字
C语言---单身狗(1)---在一个整型数组中,只有一个数字出现一次,其他数组都是成对出现的,请找出那个只出现一次的数字
|
5月前
|
C语言
C语言——oj刷题——找单身狗1
C语言——oj刷题——找单身狗1
31 0
|
5月前
|
C语言
C语言——oj刷题——找单身狗2
C语言——oj刷题——找单身狗2
35 0
|
6月前
|
C语言
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)(下)
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)
40 0
|
6月前
|
C语言
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)(上)
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)
107 0
|
6月前
|
机器学习/深度学习 存储 C语言
【C语言】找单身狗问题
【C语言】找单身狗问题
43 0
|
11月前
|
C语言
C语言第三十一弹---找单身狗
C语言第三十一弹---找单身狗
|
12月前
|
C语言
【C语言刷题】找单身狗、模拟实现atoi
【C语言刷题】找单身狗、模拟实现atoi
60 0