Алгоритм, который находит начало и конец множества подмассивов?

поэтому у меня есть этот вопрос в C:

Для массива, который содержит только нули и единицы (пример: [1,1,0,0,0,0,1,0,1,0,1,1]). Мне нужно найти начало «кольцевого интервала» и конец того же «кольцевого интервала» (таких колец может быть много, нам нужно будет сохранить начало и конец каждого из них в матрице из двух столбцов. )

«Молчание» - это когда не менее двух нулей стоят рядом друг с другом. (в данном массиве подмассив [0,0,0,0] молчит.

«Интервал звонка» - это когда тишина не возникает. (пример в данном массиве, подмассив [1,1] (первые 2 значения) и подмассив [1,0,1,0,1,1] (конец массива)).

Поэтому нам нужно сохранить [0,1] в первой строке матрицы. затем [6,11]. поскольку второй подмассив начинается с 6-го индекса и заканчивается 11-м.

Я не могу описать это лучше, это на другом языке и немного сложнее, чем это ... Надеюсь, вы понимаете!

Примеры: Array = [0,0,0,0,1,0,1,1,1,0,0,0,1,0,0] Матрица будет: [4,8] [12,12]

Массив = [1,0,0,1,1] Матрица будет: [0,0] [3,4]

Спасибо!


c arrays sequence algorithm sub-array
person Buk Lau    schedule 25.05.2017    source источник
comment
что ты уже испробовал? Почему в первом примере подмассив [1, 1, 0] не является кольцом? Он не содержит последовательных нулей.   -  person kraskevich    schedule 25.05.2017
comment
[1, 1, 0] не является кольцом, потому что за 0 следует еще один 0. После [1, 1] идет тишина.   -  person Buk Lau    schedule 25.05.2017
comment
Что мешает вам самому его кодировать? Прямо сейчас, кажется, немного дай мне код.   -  person The Archetypal Paul    schedule 25.05.2017
comment
Что произойдет, если в конце массива будет один ноль? Это ноль в кольцевом интервале или нет?   -  person The Archetypal Paul    schedule 25.05.2017
comment
@ Архетип Павел, это считается в интервале звонков, да. Я создал код, который немного беспорядочный в Matlab, это около O (N ^ 2). Мне было интересно, можно ли сделать меньше, чем в C. Я могу опубликовать свой код, если хотите   -  person Buk Lau    schedule 25.05.2017
comment
Очевидно, это можно сделать за O (N). Просто пройдитесь по массиву, отслеживая количество видимых последовательных нулей. Начните со счетчика как 2, увеличивайте, если текущий элемент равен нулю, если сейчас два, мы только что завершили прогон, поэтому сохраните текущий индекс как конец. Если текущий элемент равен 1, то, если счетчик равен нулю, двигайтесь дальше (все еще в интервале), если он на 1 ход (все еще в беге), если два или более, мы только что начали прогон, поэтому сохраните этот индекс как начало. Установите счетчик на ноль. Поправка на конец массива оставлена ​​читателю.   -  person The Archetypal Paul    schedule 25.05.2017

Ответы (1)


arrow_upward
1
arrow_downward

У меня есть простой алгоритм, который вы можете легко перевести на C, немного поработав. Вы также можете перевести его практически на любой другой язык:

Шаг 1) создайте два логических значения. Одно будет истинным, если в настоящее время существует "тишина", другое будет истинным, если последнее увиденное значение было нулем. Оба эти утверждения должны быть правдой. Если мы не предполагаем, что перед первым элементом массива стоит бесконечное количество нулей, тогда возникнут проблемы, если первое число в массиве равно нулю.

Шаг 2) переберите массив и проверьте одно из двух условий: a) Если вы видите 1, установите для тишины значение false, а для previousZero - значение false. Если это 1 нарушает тишину, сохраните это значение, так как оно является началом вашего следующего диапазона. б) Если значение равно нулю и тишины нет, установите для previousZero значение true. Если previousZero уже был истинным, вы достигли тишины, поэтому установите для тишины значение true и сохраните начальную и конечную позиции в выходном массиве. В этой ситуации вашей конечной позицией будет текущая позиция -2, чтобы учесть только что изученные нули.

Шаг 3) после того, как вы перебрали весь массив, вам нужно убедиться, что вы не закончили на допустимом диапазоне. если молчание ложно, вы знаете, что закончили на допустимом диапазоне. сохраните этот диапазон в выходном массиве, используя начальное значение, которое вы сохранили в своем цикле, и конец массива в качестве конечного значения.

Этот алгоритм работает в линейном времени. Вот какой-то псевдокод, который поможет вам начать реализацию на C или на любом другом языке, который вы выберете.

findRing(Array arr)
    bool silence = true, previousZero = true;
    int currentBegin = 0, currentEnd = 0;
    for( int i = 0; i<arr.length; i++) { 
        if(arr[i] == 1)
            if(silence == true)
                currentBegin = i;
            silence = false;
            previousZero = false;
        else if(arr[i] == 0 && silence == false)
            if(previousZero)
                silence = true;
                currentEnd = 1-2;
                addToOutput(currentBegin, currentEnd);
            else
                previousZero = true;
    }
    if(silence == false)
        currentEnd = arr.length - 1;
        addToOutput(currentBegin, currentEnd);

Я реализовал этот псевдокод на C ++ и получил те же результаты, что и вы в своих примерах. Это должно быть легко реализовать на C или Matlab, как вы упомянули, и работает за время O (n).

person Jayson Boubin    schedule 25.05.2017
comment
Спасибо за ваш ответ! Я перевел его, и он работал нормально, за исключением случаев, когда массив начинается с [0,1 ...]. он не считает первый 0 в начале массива как часть первого интервала звонка. но я установил для этого отдельный код. Я исправил эту строку также currentEnd = 1-2; на currentEnd = i-2;. Я все это очень ценю! мой код был около 60 строк в O (N ^ 2) .. действительно грязный и ужасный. ты спас мне день. Спасибо. - person Buk Lau; 25.05.2017
comment
Ой, да, я не учел начальный ноль. Виноват. Рад, что смог помочь! - person Jayson Boubin; 25.05.2017