代码之家 › 专栏 › 技术社区 › Snowman

Java数组,查找重复

arrays java

Snowman · 技术社区 · 16 年前

我有一个数组,正在查找重复项。

duplicates = false;
for(j = 0; j < zipcodeList.length; j++){
    for(k = 0; k < zipcodeList.length; k++){
        if (zipcodeList[k] == zipcodeList[j]){
            duplicates = true;
        }
    }
}

但是,当没有重复项时,此代码不起作用。为什么?

13 回复 | 直到 8 年前

135

Community Mohan Dere 9 年前

在鼻子上回答..

duplicates=false;
for (j=0;j<zipcodeList.length;j++)
  for (k=j+1;k<zipcodeList.length;k++)
    if (k!=j && zipcodeList[k] == zipcodeList[j])
      duplicates=true;

编辑以切换 .equals() 回到 == 因为我在你用的地方读过书 int 这在最初的问题中并不清楚。还设置 k=j+1 ,将执行时间减半,但仍为o(n ^二 )

一种更快(极限)的方式

这是一种基于哈希的方法。你得为自动氧化买单,但它是O(N)而不是O(N) ^二 )一个有进取心的人会找到一个基于int的原始散列集(apache或google集合中就有这样的东西,我认为)。

boolean duplicates(final int[] zipcodelist)
{
  Set<Integer> lump = new HashSet<Integer>();
  for (int i : zipcodelist)
  {
    if (lump.contains(i)) return true;
    lump.add(i);
  }
  return false;
}

向HuyLe鞠躬

见 HuyLe's answer 对于或多或少的O(N)解决方案,我认为需要几个附加步骤:

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];
   java.util.Arrays.fill(bitmap, false);
   for (int item : zipcodeList)
     if (!bitmap[item]) bitmap[item] = true;
     else return true;
   }
   return false;
}

或者只是为了紧凑

static boolean duplicates(final int[] zipcodelist)
{
   final int MAXZIP = 99999;
   boolean[] bitmap = new boolean[MAXZIP+1];  // Java guarantees init to false
   for (int item : zipcodeList)
     if (!(bitmap[item] ^= true)) return true;
   return false;
}

这有关系吗?

嗯,所以我做了一个小基准测试,这在所有地方都是不确定的,但代码如下:

import java.util.BitSet;

class Yuk
{
  static boolean duplicatesZero(final int[] zipcodelist)
  {
    boolean duplicates=false;
    for (int j=0;j<zipcodelist.length;j++)
      for (int k=j+1;k<zipcodelist.length;k++)
        if (k!=j && zipcodelist[k] == zipcodelist[j])
          duplicates=true;

    return duplicates;
  }


  static boolean duplicatesOne(final int[] zipcodelist)
  {
    final int MAXZIP = 99999;
    boolean[] bitmap = new boolean[MAXZIP + 1];
    java.util.Arrays.fill(bitmap, false);
    for (int item : zipcodelist) {
      if (!(bitmap[item] ^= true))
        return true;
    }
    return false;
  }

  static boolean duplicatesTwo(final int[] zipcodelist)
  {
    final int MAXZIP = 99999;

    BitSet b = new BitSet(MAXZIP + 1);
    b.set(0, MAXZIP, false);
    for (int item : zipcodelist) {
      if (!b.get(item)) {
        b.set(item, true);
      } else
        return true;
    }
    return false;
  }

  enum ApproachT { NSQUARED, HASHSET, BITSET};

  /**
   * @param args
   */
  public static void main(String[] args)
  {
    ApproachT approach = ApproachT.BITSET;

    final int REPS = 100;
    final int MAXZIP = 99999;

    int[] sizes = new int[] { 10, 1000, 10000, 100000, 1000000 };
    long[][] times = new long[sizes.length][REPS];

    boolean tossme = false;

    for (int sizei = 0; sizei < sizes.length; sizei++) {
      System.err.println("Trial for zipcodelist size= "+sizes[sizei]);
      for (int rep = 0; rep < REPS; rep++) {
        int[] zipcodelist = new int[sizes[sizei]];
        for (int i = 0; i < zipcodelist.length; i++) {
          zipcodelist[i] = (int) (Math.random() * (MAXZIP + 1));
        }
        long begin = System.currentTimeMillis();
        switch (approach) {
        case NSQUARED :
          tossme ^= (duplicatesZero(zipcodelist));
          break;
        case HASHSET :
          tossme ^= (duplicatesOne(zipcodelist));
          break;
        case BITSET :
          tossme ^= (duplicatesTwo(zipcodelist));
          break;

        }
        long end = System.currentTimeMillis();
        times[sizei][rep] = end - begin;


      }
      long avg = 0;
      for (int rep = 0; rep < REPS; rep++) {
        avg += times[sizei][rep];
      }
      System.err.println("Size=" + sizes[sizei] + ", avg time = "
            + avg / (double)REPS + "ms");
    }
  }

}

ncReal:

Trial for size= 10
Size=10, avg time = 0.0ms
Trial for size= 1000
Size=1000, avg time = 0.0ms
Trial for size= 10000
Size=10000, avg time = 100.0ms
Trial for size= 100000
Size=100000, avg time = 9923.3ms

和HashSet

Trial for zipcodelist size= 10
Size=10, avg time = 0.16ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.15ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.16ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms

和BitSet

Trial for zipcodelist size= 10
Size=10, avg time = 0.0ms
Trial for zipcodelist size= 1000
Size=1000, avg time = 0.0ms
Trial for zipcodelist size= 10000
Size=10000, avg time = 0.0ms
Trial for zipcodelist size= 100000
Size=100000, avg time = 0.0ms
Trial for zipcodelist size= 1000000
Size=1000000, avg time = 0.0ms

比特集赢了!

但只有一根头发….15毫秒在误差范围内 currentTimeMillis() 在我的基准测试中有一些漏洞。请注意,对于任何超过100000的列表,您只需返回 true 因为会有一个副本。事实上,如果列表类似于Random,您可以返回一个更短的列表的真正的whp。什么是道德?在这个限度内,最有效的实现是:

 return true;

你不会经常出错的。

Lie Ryan Bryan 16 年前

让我们看看您的算法是如何工作的:

an array of unique values:

[1, 2, 3]

check 1 == 1. yes, there is duplicate, assigning duplicate to true.
check 1 == 2. no, doing nothing.
check 1 == 3. no, doing nothing.
check 2 == 1. no, doing nothing.
check 2 == 2. yes, there is duplicate, assigning duplicate to true.
check 2 == 3. no, doing nothing.
check 3 == 1. no, doing nothing.
check 3 == 2. no, doing nothing.
check 3 == 3. yes, there is duplicate, assigning duplicate to true.

更好的算法:

for (j=0;j<zipcodeList.length;j++) {
    for (k=j+1;k<zipcodeList.length;k++) {
        if (zipcodeList[k]==zipcodeList[j]){ // or use .equals()
            return true;
        }
    }
}
return false;

Huy Le 8 年前

您可以使用位图来提高大数组的性能。

    java.util.Arrays.fill(bitmap, false);

    for (int item : zipcodeList)
        if (!bitmap[item]) bitmap[item] = true;
        else break;

最新消息:这是我今天的一个非常疏忽的回答,把它放在这里仅供参考。你应该参考安徒生的优秀作品 answer .

codaddict 16 年前

要检查重复项,需要比较 不同的 对。

james_bond 16 年前

因为您正在将数组的第一个元素与自身进行比较,这样它会发现即使没有重复的元素,也会有重复的元素。

doobop 16 年前

初始化k=j+1。您不会将元素与它们自己进行比较,也不会重复比较。例如,j=0,k=1和k=0,j=1比较同一组元素。这将删除k=0,j=1的比较。

KitsuneYMG 16 年前

不要使用 == 使用 .equals .

试试这个(iirc,zipcode需要实现 Comparable 为了这个工作。

boolean unique;
Set<ZipCode> s = new TreeSet<ZipCode>();
for( ZipCode zc : zipcodelist )
    unique||=s.add(zc);
duplicates = !unique;

Rolando F 10 年前

您也可以使用SET,它不允许在Java中重复。

    for (String name : names)
    {         
      if (set.add(name) == false) 
         { // your duplicate element }
    }

使用add()方法并检查返回值。如果add()返回false,则表示集合中不允许元素,这是您的副本。

geisterfurz007 user3764748 8 年前

public static ArrayList<Integer> duplicate(final int[] zipcodelist) {

    HashSet<Integer> hs = new HashSet<>();
    ArrayList<Integer> al = new ArrayList<>();
    for(int element: zipcodelist) {
        if(hs.add(element)==false) {
            al.add(element);
        }   
    }
    return al;
}

Sephiroth 10 年前

用这个方法怎么样?

HashSet<Integer> zipcodeSet = new HashSet<Integer>(Arrays.asList(zipcodeList));
duplicates = zipcodeSet.size()!=zipcodeList.length;

Huy Hóm Há»nh 8 年前

@Andersoj给出了一个很好的答案,但我也希望添加新的简单方法

    private boolean checkDuplicateBySet(Integer[] zipcodeList) {
        Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeList));
        if (zipcodeSet.size() == zipcodeList.length) {
            return true;
        }
        return false;
    }

如果zipcodelist为int[],则需要首先将int[]转换为integer[](不是自动装箱),代码 here

完整代码为:

    private boolean checkDuplicateBySet2(int[] zipcodeList) {
        Integer[] zipcodeIntegerArray = new Integer[zipcodeList.length];
        for (int i = 0; i < zipcodeList.length; i++) {
            zipcodeIntegerArray[i] = Integer.valueOf(zipcodeList[i]);
        }

        Set<Integer> zipcodeSet = new HashSet(Arrays.asList(zipcodeIntegerArray));
        if (zipcodeSet.size() == zipcodeList.length) {
            return true;
        }
        return false;
    }

希望这有帮助!

Onic Team 8 年前

打印所有重复的元素。 输出- 1 当找不到重复元素时。

import java.util.*;

public class PrintDuplicate {

    public static void main(String args[]){
        HashMap<Integer,Integer> h = new HashMap<Integer,Integer>();


        Scanner s=new Scanner(System.in);
        int ii=s.nextInt();
        int k=s.nextInt();
        int[] arr=new  int[k];
        int[] arr1=new  int[k];
        int l=0;
        for(int i=0; i<arr.length; i++)
            arr[i]=s.nextInt();
        for(int i=0; i<arr.length; i++){
            if(h.containsKey(arr[i])){
                h.put(arr[i], h.get(arr[i]) + 1);
                arr1[l++]=arr[i];
            } else {
                h.put(arr[i], 1);
            }
        }
        if(l>0)
        { 
            for(int i=0;i<l;i++)
                System.out.println(arr1[i]);
        }
        else
            System.out.println(-1);
    }
}

Jules Dupont Ahmed Elbendary 8 年前

import java.util.Scanner;

public class Duplicates {
    public static void main(String[] args) {
        Scanner console = new Scanner(System.in);
        int number = console.nextInt();
        String numb = "" + number;
        int leng = numb.length()-1;

        if (numb.charAt(0) != numb.charAt(1)) {
            System.out.print(numb.substring(0,1));
        }

        for (int i = 0; i < leng; i++){

          if (numb.charAt(i)==numb.charAt(i+1)){ 
             System.out.print(numb.substring(i,i+1));
          }
          else {
              System.out.print(numb.substring(i+1,i+2));
          }
       }
   }
}