Как проверить, имеет ли массив две разные пары совпадающих значений?

Question

public static boolean hasTwoPair(int[] arrayOfInts){  
} 

Метод должен возвращать true, если он может найти две разные пары совпадающих значений int. Поэтому, если массив был {2,2,4,7,7}, он должен возвращать true, потому что он имеет два 2s и два 7s.

Это относится только к разным значениям пары. Если это было {2,2,2,2,5}, оно вернет false, потому что это не разные значения пары.

EDIT: Это то, что я до сих пор для тела метода:

 boolean pairFound = false; 
    int pairValue; 

    for(int s = 0; s < arrayOfInts.length - 1; s++){ 
     pairValue = arrayOfInts[s]; 

     for(int c = s + 1; c < arrayOfInts.length; c++){ 
      if(pairValue == arrayOfInts[c]) 
       pairFound = true; 
     } 
    } 

    return false; //placeholder 

Я не уверен, куда идти отсюда.

Answer 1

Поскольку вы на самом деле не пробовали какой-либо код, я дам описание того, как решить эту проблему, но никакого действительного кода.

Начать с boolean как pairFound, который инициализируется false и изменения в true когда вы находите свой первый pair. Кроме того, вы будете нуждаться в int (pairValue отслеживать значения первой пары найдены (если вы нашли один).

Итерация, ищет пару. Если вы нашли пару, и pairFound ложна установите pairFound в true и установить pairValue к значению вашего первым найдено pair. Теперь держать перебор.

Если вы нашли пару и pairFound является true и пара != pairValue, то return true;. Если вы перебирать все и еще не вернули true, тогда вы можете return false.

---

Основываясь на вашем обновленном вопросе, вы довольно близки.

boolean pairFound = false; 
int pairValue = Integer.MIN_VALUE; 
//or some value that arrayOfInts will never have based on context 

for(int s = 0; s < arrayOfInts.length - 1; s++){ 
    if(arrayOfInts[s] == pairValue) { 
     continue; 
    } 
    for(int c = s + 1; c < arrayOfInts.length; c++){ 
     if(arrayOfInts[s] == arrayOfInts[c]) { 
      if(arrayOfInts[s] != pairValue) { 
       if(pairFound) {  
        return true; 
       } 
       pairValue = arrayOfInts[s]; 
       pairFound = true; 
       break; 
      } 
     } 
    } 
} 
return false; 

Answer 2

Эта задача просит вас создать список подсчетов:

• Создать структуру данных (скажем, Map<Integer,Integer>), содержащее счетчик для каждого числа из массива.
• Пройдите по карте и подсчитайте количество записей со счетом 2 и выше.
• Если вы подсчитали два или более предмета, верните true; в противном случае, возврат false.

Графы для первого примера будет выглядеть следующим образом:

V # 
- - 
2 - 2 
4 - 1 
7 - 2 

У вас есть два элемента (2 и 7) с числом 2, поэтому вернуть true.

Графы для вашего второго примера выглядит следующим образом:

V # 
- - 
2 - 4 
5 - 1 

Существует только один элемент с графом выше 2, поэтому вернуть false.

Если вы используете HashMap, этот алгоритм дает ответ в O(n).

Answer 3

Сортировка массива. Затем найдите первые два последовательных значения, которые совпадают. Если найдено, перейдите к первой записи, которая отличается от согласованной пары и повторится. Если вы дойдете до конца массива до того, как первый или второй поиск будет успешным, верните false.

Answer 4

Вам не нужно сортировать массив, чтобы дать сложность O (n * log (n)). Но ваше текущее решение еще хуже, так как оно дает сложность O (n^2). Но вам также не нужен HashMap. A Заданная и целое достаточно:

• Для каждого элемента массива сделать
  • Проверил: это элемент уже в наборе?
    • Если не поставить его в комплект
    • Если да проверить, если он равен ваш последний нашел Int пару (да, использовать в штучной упаковке Int, а не примитивный Int здесь, чтобы иметь возможность инициализировать его с null)
      • Если оно равно продолжает
      • Если это не равно
        • Если последняя пара нашла null установить его элементы дорожат
        • в противном случае вы сделали, и у вас есть по крайней мере 2 differe нт пары
• Если итерации список не доходя до последнего состояния вы не имеете 2 различных пар

Что касается реализации Set Я бы рекомендовал a HashSet

Здесь есть что сказать. Если вы его реализуете, вы не делаете никаких предположений о целых и индексируемых массивах. Все, что вам нужно, это список сопоставимых элементов. Таким образом, вы могли бы сделать подпись вашего метода гораздо более общий характер:

public static boolean hasTwoPair(Iterable<E> iterable) 

Но поскольку массивы не поддерживают генерики и Iterable интерфейс каждый клиент этого метода должен преобразовать параметры массива к Iterable с помощью метода asList() , Если это слишком неудобно, вы можете предоставить другой метод:

public static <T> boolean hasTwoPair(T[] array) 

В общем, это хорошая идея, чтобы использовать наиболее универсальный тип возможно при разработке API (также см пункт 40 и 52 в «Эффективное Java, второе издание»)