Массив Java, поиск дубликатов

Ответ 1

На носу ответьте.

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 Collections есть такая вещь, понимает.)

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 для более или менее решения 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");
    }
  }

}

С NSQUARED:

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

Победитель BITSET!

Но только за волосы....15ms находится в пределах ошибки для currentTimeMillis(), и в моем тесте есть некоторые зияющие отверстия. Обратите внимание, что для любого списка длиной более 100000 вы можете просто вернуть true, потому что будет дубликат. На самом деле, если список похож на случайный, вы можете вернуть истинный WHP для гораздо более короткого списка. Что такое мораль? В пределе наиболее эффективная реализация:

 return true;

И вы не ошибетесь очень часто.

Ответ 2

Посмотрите, как работает ваш алгоритм:

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;

Ответ 3

Вы можете использовать растровое изображение для лучшей производительности с большим массивом.

java.util.Arrays.fill(bitmap, false);
for (int item : zipcodeList)
   if (!bitmap[item]) bitmap[item] = true;
   else {
      duplicate = true;
      break;
   }

Ответ 4

Чтобы проверить наличие дубликатов, вам нужно сравнить пары отличные.

Ответ 5

Потому что вы сравниваете первый элемент массива с самим собой, поэтому он обнаруживает, что существуют дубликаты, даже если они не существуют.

Ответ 6

Инициализировать k = j + 1. Вы не будете сравнивать элементы с собой, и вы также не будете дублировать сравнения. Например, j = 0, k = 1 и k = 0, j = 1 сравнивают один и тот же набор элементов. Это позволит удалить сравнение k = 0, j = 1.

Ответ 7

Не используйте == использовать .equals.

попробуйте это вместо этого (IIRC, ZipCode необходимо реализовать Comparable, чтобы это работало.

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

Ответ 8

Как насчет использования этого метода?

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

Ответ 9

Вы также можете работать с Set, который не позволяет дублировать в Java.

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

с помощью метода add() и проверки возвращаемого значения. Если add() возвращает false, это означает, что в Set не разрешен элемент, и это ваш дубликат.