Ищете самое большое открытое пространство в массиве (C)?

Question

У меня есть массив символов, который может выглядеть так:
1 0 0 1 1 1 0 0 0 1 1 0 1

Мне нужно разработать алгоритм поиска, чтобы найти наиболее подходящее отверстие в массиве. Я не могу использовать линейный поиск. (Проблема в том, что ... я не могу придумать другого способа сделать это).

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

Answer 1

Если массив дан вам как есть (вы не создали его), так как вы знаете размер нужного вам отверстия, вы можете прыгать по размеру и смотреть вперед и назад, когда вы нажимаете 0, чтобыпосмотрим, есть ли место.

Если вы пытаетесь найти отверстие для 3 байтов и a[0] == 1, то вы знаете, что оно не будет соответствовать a[0] -> a[2].Перейдите к a[3] и посмотрите, если это 0;если это так, посмотрите вперед и назад, чтобы увидеть, есть ли место для 3 байтов.

Это только немного лучше, чем грубый метод прохождения списка начало - конец, но это лучше.

Answer 2

Итак, вам дан массив длиной n и числом k , и вас попросят найти наилучшее подходящее отверстие в массиве, близкое к k возможно, но не меньше.

Без предварительной информации о массиве и без гарантии связи между k и n , вы должны потратить O (n / k) время поиска в массиве, чтобы найти подходящее отверстие.Зачем?

Подумайте об этом так: априори, у вас есть n - k мест, где может начаться ваше отверстие наилучшего соответствия.Если вы запрашиваете один элемент в массиве, наибольшая информация, которую вы можете извлечь, заключается в том, что k местоположений в массиве не может работать:

n = 12, k = 3
array: [ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ]
                        ^-(query here, find it is occupied)  
array: [ ? ][ X ][ X ][ X ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ][ ? ]
                  Now you know the locations with X's cannot fit your data.
                  However, you can't know anything more than that.

Из этого вы можете видеть, что неважноВаш алгоритм поиска или порядок, в котором вы запрашиваете массив, вам потребуется O (n / k) доступов, чтобы определить, где находится любое отверстие, не говоря уже о наилучшем соответствии.

PS Существует также некоторая путаница с термином "линейный поиск".Для большинства это равносильно тому, что алгоритм требует линейного времени - и ваш алгоритм ДОЛЖЕН занимать линейное время.Если для вас «линейный поиск» означает последовательный поэтапный поиск по массиву, то вы можете улучшить немного на O (n) , но не более, чем к .Если k предполагается постоянной для задачи, то она выпадает, и у вас все еще остается O (n) .

Answer 3

Например, вот так?

#include <stdio.h>

int main(){
    char data[]={1,0,0,1,1,1,0,0,0,1,1,0,1};

    int dataSize = sizeof(data)/sizeof(char);
    int maxPos=-1;
    int maxLen=0;
    int pos;

    for(pos=0; pos<dataSize;){
        int skip = pos + maxLen;
        if(skip >= dataSize)break;
        if(data[pos] == 1){
            if(skip + 1 < dataSize && data[skip + 1] == 1){//add skip proc for value of 1
                pos = skip + 2;
                continue;
            }
            ++pos;
        } else {
            int len;
            if(data[skip] == 1){
                pos = skip + 1;
                continue;
            }
            for(len = 1; pos + len < dataSize && data[pos+len] == 0;++len);
            if(maxLen < len){
                maxPos = pos;
                maxLen = len;
            }
            pos += len + 1;
        }
    }
    if(maxPos == -1){
        printf("no space\n");
    } else {
        printf("The largest space is the area of length %d from position %d.\n", maxLen, maxPos);
    }

    return 0;
}

результат

The largest space is the area of length 3 from position 6.

Answer 4

Вы можете проиндексировать его перед началом.Прежде чем выполнять поиск, вы можете отсканировать массив и создать список структур, таких как:

struct SuitablePlace {
   int pos;
   ine len;
};

Затем заполните его, отсортируйте по полю len, и когда вы получите запрос области с определенным размером, вы можете использовать бинарный поисквыяснить подходящее место.