Визначення послідовності номерів списку

Я працюю на Java. У мене є невпорядкований список з 5 чисел від 0-100 без повторів. Я хотів би виявити, якщо 3 числа є послідовними без розриву.

Приклади:

[9,12,13,11,10] true
[17,1,2,3,5] true
[19,22,23,27,55] false

Що стосується того, що я намагався, нічого ще. Якби я написав його зараз, я б, ймовірно, пішов би з самим наївним підходом впорядкування чисел, потім ітераційно перевіряючи, чи існує послідовність.

7
Я не розумію - як перша послідовність true ?
додано Автор Tim Pietzcker, джерело
@Pace: Ах, так, це має бути.
додано Автор Tim Pietzcker, джерело
Три або більше. Саме це робить першу послідовність true .
додано Автор roundar, джерело
Я думаю, що питання, є 3 числа, які можуть бути організовані, щоб бути послідовними без розриву.
додано Автор Pace, джерело
Перший - це oeis.org/A007305
додано Автор arynaq, джерело
Одне питання стосовно ваших вимог, чи повинно бути саме 3 елементи або 3 чи більше елементів ?
додано Автор Adam Siemion, джерело
не виглядає як apache.commons: D пропозиція: просто реалізувати ваш алгоритм, як ви згадали. сортувати та проходити, встановлюючи прапор, якщо виявлено 3 чорнила
додано Автор user2504380, джерело

7 Відповіді

int sequenceMin(int[] set) {
    int[] arr = Arrays.copy(set);
    Arrays.sort(arr);
    for (int i = 0; i < arr.length - 3 + 1; ++i) {
        if (arr[i] == arr[i + 2] - 2) {
            return arr[i];
        }
    }
    return -1;
}

Це сортує масив і шукає потрібну послідовність, використовуючи if-заяву вище, повертаючи перше значення.


Without sorting:

(@Pace згадував про бажання не сортування.) Обмежений діапазон може використовувати ефективний "булевий масив", BitSet. Ітерація з nextSetBit є швидкою.

    int[] arr = {9,12,13,11,10};
    BitSet numbers = new BitSet(101);
    for (int no : arr) {
        numbers.set(no);
    }
    int sequenceCount = 0;
    int last = -10;
    for (int i = numbers.nextSetBit(0); i >= 0; i = numbers.nextSetBit(i+1)) {
        if (sequenceCount == 0 || i - last > 1) {
            sequenceCount = 1;
        } else {
            sequenceCount++;
            if (sequenceCount >= 3) {
                System.out.println("Sequence start: " + (last - 1));
                break;
            }
        }
        last = i;
    }
    System.out.println("Done");
4
додано
ВП вже сказав, що він має рішення, використовуючи сорт, але шукав рішення не використовуючи сортування.
додано Автор Pace, джерело

Дуже наївний (але швидший) алгоритм: (ваш масив вводиться [], якщо він містить лише 0-100 номерів, як ви сказали)

int[] nums=new int[101];
for(i=0;i0) { nums[a-1]++; }
   if (a<100) { nums[a+1]++; }
   }

Потім подивіться, чи є елемент nums [] == 3.

Може бути швидше з деякою HashMap замість масиву (і видаляє обмеження 0-100)


Змінити: На жаль, це НЕ працює, якщо дві початкові послідовності можуть бути однаковими

3
додано
Якщо хтось задається питанням, чому це не обрана відповідь, я перевірив і обрав найшвидшу відповідь. Я ціную відповідь.
додано Автор roundar, джерело
Потрібно провести цикл через масив розміром 100.
додано Автор Pace, джерело

Цей код, здається, реалізує ваші вимоги:

public class OrderdedList {
    public static void main(String[] args) {
        System.out.println(orderedWithNoGap(Arrays.asList(9, 12, 13, 11, 10)));//true
        System.out.println(orderedWithNoGap(Arrays.asList(17,1,2,3,5)));//true
        System.out.println(orderedWithNoGap(Arrays.asList(19,22,23,27,55)));//false
    }

    private static boolean orderedWithNoGap(List list) {       
        Collections.sort(list);
        Integer prev = null;
        int seq = 0;
        for(Integer i : list) {
            if(prev != null && prev+1 == i)
                seq = seq == 0 ? 2 : seq+1;
            prev = i;
        }
        return seq >= 3;
    }

}
3
додано
Це не java.util.ArrayList , це java.util.Arrays.ArrayList . Але я помилявся, це незмінність. Це лише список фіксованих розмірів. Wow, вивчив щось сьогодні! (після всіх цих років ...)
додано Автор Lukas Eder, джерело
Ви виконали це? Arrays.asList() повертає незмінний Список
додано Автор Lukas Eder, джерело
Дійсно, я не проти сортування якщо це є найбільш ефективним рішенням; однак, інтуїтивно я підозрюю, що це не так. У цьому випадку є, безумовно, більш швидкі рішення (хоча відповідь очевидно оцінюється).
додано Автор roundar, джерело
@LukasEder Повертає Список фіксованого розміру, який не java.util.ArrayList . Ви не можете add() до нього, і ви не можете видалити() з нього, але ви можете викликати set() , тому мутації на місці - гаразд.
додано Автор Petr Janeček, джерело
Вимагає такого роду, який, здавалося б, мав на увазі, що він не хотів.
додано Автор Pace, джерело
@LukasEder Так, я зробив. public static Список якList (T ... a) {return new ArrayList (a); }
додано Автор Adam Siemion, джерело
Якщо б я написав це зараз, я б, напевно, пішов би з самим наївним підходом впорядкування чисел ... , іноді найпростіші рішення - найкращі
додано Автор Adam Siemion, джерело

Виділити масив розміром 100:

private static final int MAX_VALUE = 100;

public boolean hasSequence(int [] values) {
  int [] bigArray = new int[MAX_VALUE];

  for(int i = 0; i < values.length; i++) {
    bigArray[values[i]] = 1;
  }

  for(int i = 0; i < values.length; i++) {
    index = values[i];
    if(index == 0 || index == MAX_VALUE-1) {
      continue;
    }
    if(bigArray[index-1] == 1 && bigArray[index+1] == 1) {
      return true;
    }
  }

  return false;
}
1
додано
Це рішення викине індекс поза межами винятку у другий цикл. Крім того, не повинна бути друга петля циклу через значення ints IN, а не ints між 0 і його розмір?
додано Автор roundar, джерело
Я вважаю, що рядок 7 має читати if (bigArray [значення [i] -1] == 1 && bigArray [значення [i] +1] == 1) , але перед цим слід перевірити переконайтеся, що значення [i]! = 0. Якщо цю відповідь буде відредаговано, щоб вирішити цю проблему, це буде прийнята відповідь, оскільки я вважаю, що вона найшвидша, а також дуже чітка.
додано Автор roundar, джерело
Дякуємо, це найшвидше рішення.
додано Автор roundar, джерело
Якщо index = 0 або index = bigArray.length - 1, то це викине виняток.
додано Автор roundar, джерело
Спасибі, додав, що обмеження.
додано Автор Pace, джерело
@roundar Дякуємо, очистили це. Немає необхідності перевіряти, що значення [index]! = 0, хоча.
додано Автор Pace, джерело
Я пішов вперед і замінив його формою Java і прибрав малий масив.
додано Автор Pace, джерело
Ні, це читається псевдокод, який виглядає як інша мова, про яку я можу подумати. Це також єдиний підхід, який досі є O (# пунктів у списку) і буде працювати, навіть якщо є дублікати.
додано Автор Pace, джерело

Загальні етапи алгоритму.

Step 1. Sort the array.
Step 2. There are only 3 possible groups of 3 (next to each other) in an array of length five.
indexes 0,1,2 - 1,2,3 - 2,3,4.
Step 3. Check these 3 combinations to see if the next index is 1 more than the current index.
1
додано

Як зазначила О.П. перевірте, чи містить список 3 або більше послідовних номерів

public class WarRoom {

    static final int seqCount = 3;

    public static void main(String[] args) {
        List list = new ArrayList((Arrays.asList(9, 11, 123, 511, 10)));
        for (int i : list) {
            if (seqNumbers(list, i, 0) >= seqCount) {
                System.out.println("Lucky Numbers : " + (i++) + "," + (i++) + "," + i);
            }
        }
    }

    public static int seqNumbers(List list, int number, int count) {
        if (list.contains(number)) {
            return seqNumbers(list, number + 1, count + 1);
        }
        else {
            return count;
        }
    }
}

Це не одне з найбільш ефективних рішень, але я люблю рекурсію!

0
додано

Не перевірити це, але для невеликого обсягу пам'яті можна використовувати BitSet

private static boolean consecutive(int[] input) {
    BitSet bitSet = new BitSet(100);
    for (int num : input) {
        bitSet.set(num);
    }

    bitSet.and(bitSet.get(1, bitSet.length()));//AND shift left by 1 bit
    bitSet.and(bitSet.get(1, bitSet.length()));//AND shift left by 1 bit

    return !bitSet.isEmpty();
}
0
додано
Ця відповідь використовує BitSet зі зсувом бітів для пошуку послідовних бітів у наборі
додано Автор Kelvin Ng, джерело
ІТ КПІ - Java
ІТ КПІ - Java
436 учасників