#include<iostream>
using namespace std;
// 题目：数组中只有不多于两个数字出现次数是奇数次，其他都是偶数次，求出出现奇数次的数字(不含0的数组)
//思想：
/*
（1）如果只有一个数字是奇数次，直接对数组进行按位异或运算，得到的结果就是该数
（2）如果有俩个，可以先对数组异或，得到的结果（就是两个奇数次的数字异或的结果），必定至少包含一个1，可以根据这个1在的位置，把数组分为两个部分
则两个奇数次的数字必定分别在两个部分，而相同的数次必定在同一组，则可以对两个部分分别求异或得到答案
*/
int findNumsAppear(
int arr[],
int len,pair<
int,
int>& st);
// 返回0表示没有，1表示一个，2表示2个,-1表示参数错误，没有考虑更多的情况
int count1(
int num);
// 统计int在内存中1的个数
int main()
{
pair<
int,
int>
st;
st.first=
0x80000000;
st.second=
0x80000000;
int arr[]={
2,
2,
2,
1,
1,
4,
4,
4,
4,
3,
5,
5,
6,
6,
6,
6,
7,
7,
8,
8,
9,
9,
10,
10,
11,
11};
cout<<findNumsAppear(arr,
sizeof(arr)/
sizeof(
int),st)<<
endl;
cout<<st.first<<
" "<<st.second<<
endl;
return 0;
}
int findNumsAppear(
int arr[],
int len,pair<
int,
int>&
st)
{
if(arr==NULL||len<=
0)
return -
1;
int num=arr[
0];
int count=
0;
for(
int i=
1;i<len;i++
)
num^=
arr[i];
if(num==
0)
return 0;
else // 找到num 中第一个1，让其他位置1为0 此处参考count1的方法
{
while(num)
{
if((num&(num-
1))==
0)
break;
else
num=num&(num-
1);
// 最终会保留下最高位的一个1，用来划分数组
}
}
int i=
0;
int j=len-
1;
int tmp;
while(i<j)
// 循环最终结果为i==j 左半边数组的最后个元素下标
{
while(i<j&&(arr[j]&num)==
0)
j--
;
while(i<j&&(arr[i]&num)==
num)
i++
;
if(i<
j)
{
tmp=
arr[i];
arr[i]=
arr[j];
arr[j]=
tmp;
}
}
int num1=arr[
0];
for(
int k=
1;k<=i;k++
)
num1^=
arr[k];
int num2=arr[len-
1];
for(
int k=len-
2;k>i;--
k)
num2^=
arr[k];
if(num1!=
0)
st.first=
num1;
if(num2!=
0)
st.second=
num2;
if(num1!=
0&&num2!=
0)
return 2;
else return 1;
}
int count1(
int num)
// 如果不许用位运算，直接 unsigned int n=(unsigned int)num; 用% / 计算 -1内存全部为FFFFFFFF 转为最大的unsigned int
{
int count=
0;
while(num)
{
++
count;
num=num&(num-
1);
}
return count;
}
转载于:https://www.cnblogs.com/fchy822/p/4798414.html
相关资源：数据结构—成绩单生成器
