利用位运算判断数组中是否有重复的数字

利用位运算判断数组中是否有重复的数字

解题思路：
只要满足条件
1）数组的长度为5；
2）数组中的最大值减去最小值小于5（最大值、最小值不取0）；
3）除0外没有重复的数字。
这个数组就是连续的，即可组成顺子。
代码如下：
class Solution {
public:
bool IsContinuous( vector numbers ) {
if(numbers.size() != 5)
return false;
int min = 14; // 设定最小值的初始值
int max = -1; // 设定最大值的初始值
int flag = 0; // flag用于判定数组中是否有重复值
for(int i = 0; i < 5; i++){
// 根据题意，数字的范围为1-13，若不在此范围则返回false
if(numbers[i] < 0 || numbers[i] > 13)
return false;
if(numbers[i] == 0)
continue;
// 判断数字是否重复
if(((1 << numbers[i]) & flag) > 0)
return false;
flag |= (1 << numbers[i]);
if(numbers[i] > max)
max = numbers[i];
if(numbers[i] < min)
min = numbers[i];
// 判断最大值与最小值的差是否小于5
if(max - min > 4)
return false;
}
return true;
}
};
我们用到了位运算来判断数组中是否存在重复值，它的原理简单且实用：
因为我们的数字范围为1-13，用每一个bit对应一个数字，如果出现过，那么flag上这个bit就为1，不然就是0，且用一个32bit的int型足够容纳下所有位。