Найти минимальное число во всех смежных подмассивах размера l массива размера n

Question

Минимальное число в подмассиве размера LI должно найти его для всех подмассивов массива. Есть ли другой способ, кроме сканирования всех подмассивов по отдельности.

Я имею в виду одно решение.

a[n]//the array
minimum[n-l+1]//the array to store the minimum numbers

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)
    {
        minpos=position_minimum_in_subarray(a,i,i+l-1);
    }
    else {
        if(a[minpos]>a[i+l-1]) minpos=i+l-1;
        minimum=a[minpos];
    }
}

Есть ли что-нибудь лучше, чем это?

Answer 1

Вы можете использовать двустороннюю очередь (Q) . Найдите такой способ, чтобы наименьший элемент всегда появлялся в передней части Q, а размер Q никогда не превышал L. Таким образом, вы всегда вставляете и удаляете элементы не более одного раза, принимая решение На). Я чувствую, что это достаточно подсказка, чтобы вы пошли.

Answer 2

Ответ версии Scala

def movingMin(windowSize: Int, array: Seq[Double]) = { 
    (1 to array.length - (windowSize - 1)).
        map{i => (array.take(i + (windowSize - 1)).takeRight(windowSize)).min}
}

Answer 3

Я думаю, что ваше решение в порядке, но для правильной работы оно должно выглядеть примерно так:

a[n]//the array
minimum[n-l+1]//fixed

minpos=position_minimum_in_subarray(a,0,l-1);
minimum[0]=a[minpos];
for(i=1;i<=n-l-1;i++)
{
    if(minpos=i-1)        
        minpos=position_minimum_in_subarray(a,i,i+l-1);                   
    else if(a[minpos]>a[i+l-1]) //fixed
        minpos=i+l-1; //fixed

    minimum[i] = a[minpos];
}

// Complexity Analysis :

//Time - O(n^2) in worse case(array is sorted) we will run
         "position_minimum_in_subarray" on each iteration

//Space - O(1) - "minimum array" is required for store the result

---

Если вы хотите улучшить сложность своего времени, вы можете сделать это с дополнительным пространством. Например, вы можете хранить каждый суб-массив в некотором самобалансирующемся BST (например, красно-черном дереве) и извлекать минимум на каждой итерации:

for (int i= 0; i<n; i++) {
    bst.add(a[i]);

    if (bst.length == l) {
        minimum[i-l] = bst.min;
        bst.remove(a[i - l]);            
    }
  }

 //It's still not O(n) but close.

 //Complexity Analysis :

 //Time - O(n*log(l)) = O(n*log(n)) - insert/remove in self-balancing tree
                                      is proportional to the height of tree (log)

 //Space - O(l) = O(n)