Поиск наименьшего числа k в массиве с Big-Oh (n) [duplicate]

Рассмотрим установку пакета more_itertools .

> pip install more_itertools

Он поставляется с реализацией для flatten ( source из рецептов itertools ):

import more_itertools


lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
list(more_itertools.flatten(lst))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

Начиная с версии 2.4 вы можете сгладить более сложные, вложенные итерации с помощью more_itertools.collapse ( источник , внесенный abarnet).

lst = [[1, 2, 3], [4, 5, 6], [7], [8, 9]]
list(more_itertools.collapse(lst)) 
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

lst = [[1, 2, 3], [[4, 5, 6]], [[[7]]], 8, 9]              # complex nesting
list(more_itertools.collapse(lst))
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

15
задан Bill the Lizard 20 September 2012 в 13:49
поделиться

11 ответов

Как уже упоминалось, существует два способа выполнить такую ​​задачу:

1) Вы можете отсортировать весь массив элементов n с помощью quicksort , heapsort или любой алгоритм сортировки O (n log n), который вы хотите, а затем выберите наименьшие значения m в вашем массиве. Этот метод будет работать в O(n log n).

2) Вы можете использовать алгоритм выбора , чтобы fink m наименьшие элементы в вашем массиве. Потребуется время O(n), чтобы найти наименьшее значение kth , так как вы будете повторять этот алгоритм m раз, общее время будет m x O(n) = O(n).

0
ответ дан aliboy38 26 August 2018 в 18:38
поделиться

вам нужно будет найти k'th наименьший элемент, используя «алгоритм выбора», который является O (n), а затем снова итерации массива и возврата каждого элемента, который меньше / равен ему. алгоритм выбора: http://en.wikipedia.org/wiki/Selection_algorithm вам придется обратить внимание, если у вас есть повторы: вам нужно будет убедиться, что вы не возвращаете больше k элементов (это возможно, если вы, например, имеете 1,2, ..., k, k, k, ...) EDIT: полный алгоритм и возвращающий список в соответствии с запросом: пусть массив будет A

 1. find the k'th element in A using 'selection algorithm', let it be 'z'
 2. initialize an empty list 'L'
 3. initialize counter<-0
 4. for each element in A: 
 4.1. if element < z: 
   4.1.1. counter<-counter + 1 ; L.add(element)
 5. for each element in A:
 5.1. if element == z AND count < k:
   5.1.1. counter<-counter + 1 ; L.add(element)
 6. return L

обратите внимание, что требуется 3-я итерация, если в вашем списке могут быть дубликаты. если он не может - это бесполезно, просто измените условие в 4.1 на & lt; =. также обратите внимание: L.add вставляет элемент в связанный список и, следовательно, O (1).

23
ответ дан amit 26 August 2018 в 18:38
поделиться

Я сделал это в интервью раньше, и один из самых элегантных / эффективных способов сделать это:

O(n log k). 
with space: O(k) (thanks, @Nzbuu)

В основном вы собираетесь использовать максимальную кучу размера, ограниченного до k. Для каждого элемента массива проверьте, меньше ли он (только O (1)). Если это так, поместите это в кучу (O (log k)) и удалите макс. Если он больше, перейдите к следующему пункту.

Конечно, куча не дает отсортированный список из k элементов, но это можно сделать в O (k log k), что легко.

Точно так же вы можете сделать то же самое для поиска наибольших k-элементов, и в этом случае вы будете использовать мини-кучу.

30
ответ дан Chet 26 August 2018 в 18:38
поделиться

Можно найти k наименьшее из n элементов в O(n) времени (под которым я имею в виду истинное O(n) время, а не O(n + some function of k)). Обратитесь к статье Википедии «Алгоритм выбора» , особенно к подразделам «неупорядоченная частичная сортировка» и «медианный отбор в качестве сводной стратегии», а также к статье «Медиана медианов» для основной части, которая делает это O(n).

1
ответ дан David K 26 August 2018 в 18:38
поделиться

Предполагая, что вы пытаетесь показать наименьшие числа K, вы можете использовать алгоритм выбора Хора, чтобы найти k-е наименьшее число. Это разбивает массив на меньшие числа, k-е число и большее число.

4
ответ дан Jerry Coffin 26 August 2018 в 18:38
поделиться

Как использовать кучу для хранения значений. Эта стоимость равна n, когда вы проходите каждое значение в массиве.

Затем переходите через кучу, чтобы получить наименьшие значения k.

Время выполнения равно O (n) + O (k ) = O (n)

Конечно, пространство памяти теперь O (n + n)

0
ответ дан Matthew Chan 26 August 2018 в 18:38
поделиться

Другой метод - используйте QuickSelect Algorithm, и результатом будут все элементы слева от возвращаемого результата. Средняя временная сложность была бы O (n), а в худшем случае она была бы O (n ^ 2). Сложность пространства была бы O (1).

0
ответ дан Neel Shah 26 August 2018 в 18:38
поделиться

Я не знаю точно, что вы ищете, но довольно простое время O (n * k) и O (k). Это самый большой К, поэтому ему нужно было бы наброситься на него.

Для грубых для min k (результат) можно заменить кучу

private int[] FindKBiggestNumbersM(int[] testArray, int k)
{
    int[] result = new int[k];
    int indexMin = 0;
    result[indexMin] = testArray[0];
    int min = result[indexMin];

    for (int i = 1; i < testArray.Length; i++)
    {
        if(i < k)
        {
            result[i] = testArray[i];
            if (result[i] < min)
            {
                min = result[i];
                indexMin = i;
            }
        }
        else if (testArray[i] > min)
        {
            result[indexMin] = testArray[i];
            min = result[indexMin];
            for (int r = 0; r < k; r++)
            {
                if (result[r] < min)
                {
                    min = result[r];
                    indexMin = r;
                }
            }
        }
    }
    return result;
}
1
ответ дан paparazzo 26 August 2018 в 18:38
поделиться

Наилучшее возможное решение проблемы заключается в следующем. Используйте Quick sort, чтобы найти опорные точки и отбросить часть, где этот k-й элемент не лежит, и рекурсивно найти следующий опорный элемент. (Это kth Max finder, вам нужно изменить условие if else, чтобы сделать его kth Min Finder). Вот код JavaScript -

  // Complexity is O(n log(n))
  var source = [9, 2, 7, 11, 1, 3, 14, 22];

  var kthMax = function(minInd, MaxInd, kth) {
      // pivotInd stores the pivot position 
      // for current iteration
      var temp, pivotInd = minInd;
      if (minInd >= MaxInd) {
        return source[pivotInd];
      }

      for (var i = minInd; i < MaxInd; i++) {
        //If an element is greater than chosen pivot (i.e. last element)
        //Swap it with pivotPointer element. then increase ponter
        if (source[i] > source[MaxInd]) {
          temp = source[i];
          source[i] = source[pivotInd];
          source[pivotInd] = temp;
          pivotInd++;
        }
      }
      // we have found position for pivot elem. 
      // swap it to that position place .
      temp = source[pivotInd];
      source[pivotInd] = source[MaxInd];
      source[MaxInd] = temp;

      // Only try to sort the part in which kth index lies.
      if (kth > pivotInd) {
        return kthMax(pivotInd + 1, MaxInd, kth);
      } else if (kth < pivotInd) {
        return kthMax(minInd, pivotInd - 1, kth);
      } else {
        return source[pivotInd];
      }

    }
    // last argument is kth-1 , so if give 2 it will give you,
    // 3rd max which is 11

  console.log(kthMax(0, source.length - 1, 2));
1
ответ дан sapy 26 August 2018 в 18:38
поделиться

Это можно сделать в ожидаемом линейном времени (O (n)). Сначала найдите наименьший элемент kth массива (используя метод разбиения на разделы для нахождения статистики порядка kth), а затем просто проведите по петле, чтобы проверить, какие элементы меньше наименьшего элемента kth. Обратите внимание, что это работает правильно только для отдельного элемента.

Вот код в c:

    /*find the k smallest elements of an array in O(n) time. Using the Kth order 
statistic-random pivoting algorithm to find the kth smallest element and then looping 
through the array to find the elements smaller than kth smallest element.Assuming 
distinct elements*/


    #include <stdio.h>
    #include <math.h>
    #include <time.h>
    #define SIZE 10
    #define swap(X,Y) {int temp=X; X=Y; Y=temp;}


    int partition(int array[], int start, int end)
    {
        if(start==end)
            return start;
        if(start>end)
            return -1;
        int pos=end+1,j;
        for(j=start+1;j<=end;j++)
        {       
            if(array[j]<=array[start] && pos!=end+1)
            {
                swap(array[j],array[pos]);
                pos++;
            }
            else if(pos==end+1 && array[j]>array[start])
                pos=j;
        }
        pos--;
        swap(array[start], array[pos]);
        return pos;
    }

    int order_statistic(int array[], int start, int end, int k)
    {
        if(start>end || (end-start+1)<k)
            return -1;                   //return -1 
        int pivot=rand()%(end-start+1)+start, position, p;
        swap(array[pivot], array[start]);
        position=partition(array, start, end);
        p=position;
        position=position-start+1;                  //size of left partition
        if(k==position)
            return array[p];
        else if(k<position)
            return order_statistic(array, start,p-1,k);
        else
            return order_statistic(array,p+1,end,k-position);
    }


    void main()
    {
        srand((unsigned int)time(NULL));
        int i, array[SIZE],k;
        printf("Printing the array...\n");
        for(i=0;i<SIZE;i++)
            array[i]=abs(rand()%100), printf("%d ",array[i]);
        printf("\n\nk=");
        scanf("%d",&k);
        int k_small=order_statistic(array,0,SIZE-1,k);
        printf("\n\n");
        if(k_small==-1)
        {
            printf("Not possible\n");
            return ;
        }
        printf("\nk smallest elements...\n");
        for(i=0;i<SIZE;i++)
        {
            if(array[i]<=k_small)
                printf("%d ",array[i]);
        }
    }
1
ответ дан sudeepdino008 26 August 2018 в 18:38
поделиться

Просто отсортируйте массив с помощью Merge Sort, а затем напечатайте первое число k, в худшем случае будет n * log2 (n).

0
ответ дан Tamer Shlash 26 August 2018 в 18:38
поделиться
Другие вопросы по тегам:

Похожие вопросы: