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，也就是第一个匹配结果，此方法效率较高。