消失的数字（c语言实现）
消失的数字题目介绍
方法一我们使用异或操作符实现。介绍一下^操作符性质就是首先
0^a=a； a^a=0;然后异或操作符还满足交换律。比如a ^ b ^ c ^a= a ^ a ^b ^c;
我们可以通过这样的性质实现这个代码，上面的题目中我们发现数组中缺少一个元素2，我们通过这样的方式来
我们先把数组中的数字遍历一遍，然后在遍历一遍0到n的数字。
#include<stdio.h>
int find_num(int* str, int sz)
{
int i = 0;
int val = 0;
for (i = 0; i < sz; i++)
{
val ^= str[i];
}
for (i = 0; i <= sz; i++)
{
val ^= i;
}
return val;
}
int main()
{
int arr[] = { 0,1,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret=find_num(arr, sz);
printf("%d\n", ret);
return 0;
}
第二种方法就是我们可以通过求和法，求0到n所有的数字之和然后减去数组的元素就可以得到消失的数字。
int find_num(int arr[], int sz)
{
int sum = sz * (sz + 1) / 2;
int i = 0;
for (i = 0; i < sz; i++)
{
sum -= arr[i];
}
return sum;
}
int main()
{
int arr[] = { 0,1,3 };
int sz = sizeof(arr) / sizeof(arr[0]);
int ret=find_num(arr, sz);
printf("%d\n", ret);
return 0;
}
进阶版本，求数组中只出现一次的数字
给定一个数组，数组的元素只出现一次例如{1，2，3，4，5，1，2，3，4，6}
如何求出数组中的只出现一次的数字。
方法一我们可以直接遍历一遍数组，数组中出现俩次的数字就跳过，相等的就返回。
void find_num(int* str, int sz)
{
int i = 0;
int num = 0;
for (i = 0; i < sz; i++)
{
int j = 0;
num = str[i];
for (j = 0; j < sz; j++)
{
if (i == j)
{
continue;
}
if (str[i] == str[j])
{
break;
}
}
if (j == sz)
{
printf("%d ", str[i]);
}
}
}
int main()
{
int arr[] = {1,2,3,4,5,1,2,3,4,6};
int sz = sizeof(arr) / sizeof(arr[0]);
find_num(arr, sz);
return 0;
}
第二种使用^操作符计算
首先我们在刚刚消失的数字游戏中了解了异操作符的相关的特性，我们也可以使用这样的特点来查找。
5 101
6 110
根据^的特性相同为0相异为1的方法得到011。我们可以让二进制末尾为1的分为一组，我们可以分为1 1 3 3 5和2 2 4 4 6俩组，我们可以在俩个数组中异或 得到只出现一次的数字。
void find_num(int* str, int sz)
{
int i = 0;
int val = 0;
for (i = 0; i < sz; i++)
{
val ^= str[i];
}
int pos = 0;
for (i = 0; i < 32; i++)
{
if (((val >> i) & 1) == 1)
{
pos = i;
break;
}
}
int num1 = 0;
int num2 = 0;
for (i = 0; i < sz; i++)
{
if (((str[i] >> pos) & 1) == 1)
{
num1 ^= str[i];
}
else
{
num2 ^= str[i];
}
}
printf("%d %d", num1, num2);
}
int main()
{
int arr[] = {1,2,3,4,5,1,2,3,4,6};
int sz = sizeof(arr) / sizeof(arr[0]);
find_num(arr, sz);
return 0;
}
这些题目要求我们要知道位操作符的特点：
&：二进制对应位两个都为1则为1，否则为0。
|：二进制对应位两个都为0则为0，否则为1。
^：二进制对应位相同则为0，不同则为1
原文地址：https://blog.csdn.net/2402_82552926/article/details/143787864
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！