Question

判断数组中是否有重复的数字

Answer 1

1.
单循环判断数组中是否有存在重复值
这个取决于数组使用的数字，如果是字符串则没办法处理。
面试题：已知有一长度为100的无序随机整型数组，且数值范围是[1,100]，写一算法，判断数组中是否有存在重复值，要求，不得嵌套循环，不得使用递归。
方法一：1publicboolCheckRepeat(int[]a)2{3//定义一个数组测试用，思想:数组的下标和值都是上一个数组元素中的值4int[]array=newint[101];5//将数组的值都复制到测试数组中6for(inti=0;i<100;i++)7{8inta=a[i];9array[a]=a;//或者Array[a]=任何非零的数字，做标志用。10}1112//如果数组没有重复，则会填满测试数组，否则数组中将出现自动初始化的值13for(inti=1;i<101;i++)14{15//判断如果数组中有自动初始的值，则数组没有被填满16if(array[i]==0)17{18returnfalse;19}20}21returntrue;22}上述方法收集自网络，这个方法写的很巧妙，思路也很清晰，但看起来还是有些多余代码，尽管满足了题目要求，只使用了一重循环，但算法中使用了两个循环进行判断，感觉还不够简洁，下面改造算法为一个单循环：方法二：1publicboolCheckRepeat(int[]a)2{3int[]array=newint[101];//数组元素值初始化默认为04for(inti=0;i<100;i++)5{6inta=a[i];7if(array[a]!=0)//说明此元素已经赋过值了，即发生了重复8returntrue;9else10array[a]=1;//做标志用,也可赋任何不为0的数11}12returnfalse;13}
2.字符串数组的情况Java代码/***判断数组内有无重复元素
*@paramargs
*@returntrue有重复|false无重复*/publicstaticbooleanhasRepeat(Object[]args){
Set<ObjecttempSet=newHashSet<Object();
for(inti=0;i<args.length;i++){
tempSet.add(args[i]);}if(args.length==tempSet.size()){
returnfalse;}else{returntrue;}}/** * 判断数组内有无重复元素 * @param args * @return true 有重复 | false 无重复 */ public static boolean hasRepeat(Object[] args){ Set<Object tempSet = new HashSet<Object(); for (int i = 0; i < args.length; i++) { tempSet.add(args[i]); } if(args.length == tempSet.size()){ return false; }else{ return true; } }
还可以通过其他方法：
1.两个for循环，依次判断是否相等，或先调用Arrays.sort()，然后再用Arrays.binarysearch()比较
2.把数组转化成一个用特殊字符分隔的字符串，然后用正则表达式里的\1，也就是第一个匹配结果，此方法效率较高。

Answer 2

解题思路：
只要满足条件
1）数组的长度为5；
2）数组中的最大值减去最小值小于5（最大值、最小值不取0）；
3）除0外没有重复的数字。
这个数组就是连续的，即可组成顺子。
代码如下：
class Solution {
public:
bool IsContinuous( vector<int> 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型足够容纳下所有位。

Answer 3

// 判定一个数组中是否存在相同的数。
// 拿每个数和它后面所有的数比较，有相同的就返回真。
// 全部比较完都没有相同的就返回假。
int HasIdentical(const int* arr, int n)
{
int i = 0, j = 0;
for (i = 0; i < n; ++i)
{
for (j = i + 1; j < n; ++j)
{
if (arr[i] == arr[j])
{
return 1;
}
}
}

return 0;
}

// 按照你的意思，这个函数可以这样改写：
int judgement(int a, int b, int c, int d, int e, int f, int g, int h, int i)
{
int arr[9] = { 0 };
arr[0] = a; arr[1] = b; arr[2] = c; arr[3] = d; arr[4] = e;
arr[5] = f; arr[6] = g; arr[7] = h; arr[8] = i;

return !HasIdentical(arr, 9);
}