一个算法题,亟待解决

Question

100个整数（取值范围为[1,100]，存在一个数组arr[100]中 
请写一个函数，判断该数组内是否有重复的数？ 
限制：时间复杂度为O（N）与空间复杂度O（1） 
另：在该限制下，能判断是哪个（或哪些）数字重复么？

Answer 1

由于加了这个限制，要不然5050是个相当好的选择
public static void test(int[] array) {
int[] flag = new int[100]; for (int i : array)
flag[i - 1] += 1; for (int i : flag)
if (i > 1)
System.out.println(i);
}

Answer 2

我想了个方法，大家看行不？已知：100个数存在arr[100]中，取值范围1-100定义标志数组tag[100],初始化全是0  （这个空间复杂度算不算O（1））
读取arr[100]对所有的arr[i] 置tag[i-1]=1
遍历tag[100] 如果存在tag[j]==0那么有重复的，并且j+1在arr[100]中是空缺的
这个方法时间复杂度为2×100，达到O（n）
如果定义了tag空间复杂度算O(n)的话，那么不要tag数组，每读到arr[i]时，把arr[arr[i]-1]的数置为负值，如果已经为负数，则判为重复关于判断重复的数，只要在上面的方法中修改tag[i]为1之前发现值已经是1了，那么i+1是重复的数字

Answer 3

这方法不能判断 那个数重复...
用byte 类型的做(设为b[100]),遍历arr[100], 让 b[i-1]++;
这下连重复几个都知道拉...
可惜,我觉得不太合题意,貌似空间不是O(1)

Answer 4

用TreeSet(),再.size()方法，要是返回的是100，就证明没有重复的了

Answer 5

时间复杂度和空间复杂度的知识我忘记了。
我这里想了两个办法，不知道是否符合要求。
一、先创建一个与待处理数组同样大小的整数数组，然后，把数据copy到新数组中，对新数组进行排序，然后比较是否有相同的，就可以了。
这个方法，可以判断，具体重复的数字，以及重复的次数。
二、创建一个标记数组（或者一个BitSet），由于待处理的数组，其内容，是[1,100]所以，标记数组的下标就可以表示待处理数组中是否存在该整数。
标记数组为boolean型数组（或使用BitSet）时，只可以表示是否存在该整数；
标记数组为int型数组时，数组元素的大小，可以用来表示待处理数组中某个元素出现的次数。
处理过程，就是，先创建标记数组，然后，把待处理数组的关系映射到标记数组中，最后，判断标记数组的内容可以得到所要得到的答案。

Answer 6

注意一下空间复杂度,如果另外new出一个数组的话,我已经实现了,现在要解决的是要空间复杂度为O(1)

Answer 7

不让创建数组，那，声明三个变量总可以把，声明两个变量int max,min,total;
把待处理数组遍历一遍，求出它的最大值、最小值和所有数的和。
数组里面有不重复的数的条件，我想应该是：最大值是100，最小值是1，所有数的和是5050

Answer 8

不需要新数组，直接在传入的数组上做标记就可以了。boolean hasDuplication(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] == 0) continue;
        int j = arr[i] - 1;
        if (arr[j] == 0) return true;
        do {
            int temp = arr[j] - 1;
            arr[j] = 0;
            j = temp;
        } while (j != i && arr[j] != 0);
        if (j == i) {
            arr[j] = 0;
        } else {
            return true;
        }
    }
    return false;
}

Answer 9

public class Test1 {    private final static char[] HEX = "0123456789abcdef".toCharArray();    public static void main(String[] args) throws Exception {
        
        // initialize
        final int count = 100;        
        int[] num = new int[count];
        for(int i = 0; i < count; i++) {
            num[i] = i + 1;
        }
        num[2] = 5;
        num[5] = 11;
        num[14] = 19;
        
        final int container = 30;
        int[] record = new int[(count + container - 1) / container];
        for(int i = 0; i < count; i++) {
            int k = num[i] - 1;
            if((record[k / container] >> (k % container) & 1) == 1) {
                System.out.println("duplicate number: " + num[i]);
            }
            record[k / container] |= 1 << (k % container);        
        }
        
        for(int i = 1; i <= count; i++) {
            if((record[(i - 1)/ container] >> ((i - 1) % container) & 1) == 0) {
                System.out.println("missing number: " + i);
            }
        }
    }
}

Answer 10

import java.util.*;
public class JudgeMulti {
public static void main(String[] args) {
int arr[] = new int[101];
int j;
// 初始化数组
for (int i = 1; i <= 100; i++) {
Random rnd = new Random();
arr[i] = Math.abs(rnd.nextInt() % 99)+1;
if ((i - 1) % 10 == 0)
System.out.println();
System.out.print(arr[i] + "   ");
}
System.out.println();
// 判断有无重复数，如果有输出重复数
for (int i = 1; i <= 100; i++) {
j = Math.abs(arr[i]);
if (arr[j] < 0)
System.out.println("arr[" + i + "]=" + j + "有重复");
else
arr[j] = arr[j] * (-1);
}
// 目前的缺点是只知道某个数有重复，不知道它重复的另一个数在什么位置
// 如果想知道a[i]=a[j]=k的中i,j的值得话，需要定义另外一个数组，影响空间复杂度
}
}
下面是结果：44   73   65   48   63   28   4    41   87   30   
13   74   21   55   60   46   16   70   54    1   
20   71   61   87   17   27   58   31   35   69   
9    57    9   20   56   57   40   59   17   53   
88   46   62   76   12   30   59    5   89    6   
48   14   93   91   72   46   75   25   19   35   
96   23    3    3   38   65   19   16   94   22   
77   93   11   16   77   27   93   59   85   51   
62   77   30   59   58   95   30   40   65   79   
20   61   64   30   15   12   73   22    7   40   
arr[24]=87有重复
arr[33]=9有重复
arr[34]=20有重复
arr[36]=57有重复
arr[39]=17有重复
arr[42]=46有重复
arr[46]=30有重复
arr[47]=59有重复
arr[51]=48有重复
arr[56]=46有重复
arr[60]=35有重复
arr[64]=3有重复
arr[66]=65有重复
arr[67]=19有重复
arr[68]=16有重复
arr[72]=93有重复
arr[74]=16有重复
arr[75]=77有重复
arr[76]=27有重复
arr[77]=93有重复
arr[78]=59有重复
arr[81]=62有重复
arr[82]=77有重复
arr[83]=30有重复
arr[84]=59有重复
arr[85]=58有重复
arr[87]=30有重复
arr[88]=40有重复
arr[89]=65有重复
arr[91]=20有重复
arr[92]=61有重复
arr[94]=30有重复
arr[96]=12有重复
arr[97]=73有重复
arr[98]=22有重复
arr[100]=40有重复

Answer 11

复杂度是常数是指空间/时间不依赖于其他变量吧？
也就是说有N个值，只要是分配固定长度的内存，空间复杂度都是O(1)；只有要分配长度为N的内存，空间复杂度才是O(N).
不知道我说的对不对？

Answer 12

我感觉你的算法里用的   int[] record = new int[(count + container - 1) / container];这个就是问题规模ｃｏｕｎｔ的函数，空间复杂度不能算ｏ（１）吧

Answer 13

简单写了个main。写完之后发现和28楼用了相同的原理。
public static void main(String[] args) {
int len=5;
int arr[]=new int[len];
Random r=new Random();
for(int i=0;i<arr.length;i++){
arr[i]=r.nextInt(len);
System.out.println(arr[i]);
}

for(int i=0;i<len;i++){
arr[arr[i]%len]+=len;
}

for (int i = 0; i < arr.length; i++) {
if(arr[i]>len*2){//此处还可判断该数重复了几次，但不能判断重复的位置。
System.out.println("dup:"+i);
}
}

}

Answer 14

上面有个bug ，if(arr[i]>len*2){
应该是  if(arr[i]>=len*2){

Answer 15

你可以引入３个或者５个之类的常数个与问题规模无关的变量．我感觉原数组最好不要变.
所以我感觉这个题目很难实现．记得看过一个证明：去除数组中重复的数的最快算法就是先排序再扫描了.这样的话,别的不说,排序就需要O(nlgn)的时间了.
当然如果数组有序的话,问题就容易解决了.

Answer 16

这个算法还是不完美的
比如下面这个数组9  7  6  8  5  5  1  5  5  4  
arr[6]=5有重复
arr[8]=5有重复
arr[9]=5有重复
5重复了四次，但只能找到三个