单身狗1和单身狗2(C语言版)

简介: 单身狗1和单身狗2(C语言版)

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;
}

 

相关文章
|
7月前
|
算法 C语言
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2
55 0
|
7月前
|
算法
leetcode:136. 只出现一次的数字(找单身狗)
leetcode:136. 只出现一次的数字(找单身狗)
28 0
|
5月前
|
算法 C语言
【C语言】单身狗问题
C语言中的单身狗问题
36 1
【C语言】单身狗问题
每日一练Day04:寻找单身狗
每日一练Day04:寻找单身狗
|
6月前
找出单身狗1,2
找出单身狗1,2
30 0
|
6月前
|
C语言
C语言——oj刷题——找单身狗2
C语言——oj刷题——找单身狗2
38 0
|
6月前
|
C语言
C语言——oj刷题——找单身狗1
C语言——oj刷题——找单身狗1
34 0
|
7月前
单身狗问题
单身狗问题
29 0
|
7月前
|
机器学习/深度学习 存储 C语言
【C语言】找单身狗问题
【C语言】找单身狗问题
53 0