Тізімнің нөмірлері дәйекті екендігін анықтау

Мен Java-де жұмыс істеймін. Менде қайталанбайтын 0-ден 100-ге дейінгі сандардағы 5 таңбалы тізім бар. Сандардың үшеуі бос орынсыз болғанын анықтағым келеді.

Мысалдар:

[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-statement арқылы қажетті мәнді іздейді, бірінші мәнді қайтарады.


Without sorting:

(@Pace сұрыптау сұралмағаны туралы айтқан.) Шектелген ауқым тиімді BitLet көмегімен «логикалық массив» пайдалана алады. 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() өзгермейтін List функциясын қайтарады
қосылды автор Lukas Eder, көзі
Шындығында, егер сұрыптауға қарсы емеспін, бұл ең тиімді шешім; алайда, интуитивті емес деп ойлаймын. Бұл жағдайда белгілі бір жылдам шешімдер бар (бірақ бұл жауап анық бағаланады).
қосылды автор roundar, көзі
@LukasEder Ол емес java.util.ArrayList болып табылатын List тіркелген өлшемді қайтарады. Сіз оған add() кодын бере алмайсыз және set() деп қоңырау шала аласыз, солайша set() орнында мутация жақсы.
қосылды автор Petr Janeček, көзі
Оператордың қалаусыз дегенді білдіретін түрі қажет.
қосылды автор Pace, көзі
@LukasEder Иә, мен жасадым. public static Тізім asList (T ... a) {жаңа 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
қосылды
Бұл шешім индексті екінші циклде шегінен тыс алып тастайды. Сондай-ақ, екінші шлейф циклы IN мәндерінен емес, 0 мен оның өлшемдерінің арасында емес.
қосылды автор roundar, көзі
7-жолда if (bigArray [values ​​[i] -1] == 1 && bigArray [мәндер [i] +1] == 1) дегенді оқуы керек, бірақ бұған дейін Егер бұл жауапты түзету үшін бұл сұраққа жауап берілсе, онда ол жауапты болады, өйткені бұл өте тез, бірақ өте анық.
қосылды автор 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
қосылды

Мұны сынамағаныңыз жөн, бірақ шағын жадқа арналған із қалдыру үшін 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, көзі