O(n)에서 길이가 n인 정렬되지 않은 배열에서 k번째로 큰 요소를 찾는 방법은 무엇입니까?

Question

나는 O(n)에서 길이가 n인 정렬되지 않은 배열에서 k번째로 큰 요소를 찾는 방법이 있다고 믿습니다.아니면 "예상" O(n) 일 수도 있습니다.어떻게 할 수 있나요?

Answer 1

이것을 찾기라고합니다 K-ther 주문 통계. 매우 간단한 무작위 알고리즘이 있습니다 (호출 QuickSelect) 복용 O(n) 평균 시간, O(n^2) 최악의 시간과 꽤 복잡한 비 랜덤 화 알고리즘 ( INTROSELECT) 복용 O(n) 최악의 시간. 정보가 있습니다 위키 백과, 그러나 그것은별로 좋지 않습니다.

필요한 모든 것이 있습니다 이 파워 포인트 슬라이드. 기본 알고리즘을 추출합니다 O(n) 최악의 케이스 알고리즘 (INTROSELECT) :

Select(A,n,i):
    Divide input into ⌈n/5⌉ groups of size 5.

    /* Partition on median-of-medians */
    medians = array of each group’s median.
    pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
    Left Array L and Right Array G = partition(A, pivot)

    /* Find ith element in L, pivot, or G */
    k = |L| + 1
    If i = k, return pivot
    If i < k, return Select(L, k-1, i)
    If i > k, return Select(G, n-k, i-k)

또한 Cormen et al.

Answer 2

당신이 진실을 원한다면 O(n) 반대로 알고리즘 O(kn) 또는 그런 것, 당신은 QuickSelect를 사용해야합니다 (기본적으로 관심이없는 파티션을 버리는 곳). 내 교수는 런타임 분석과 함께 훌륭한 글을 가지고 있습니다.참조)

QuickSelect 알고리즘은 분류되지 않은 배열의 가장 작은 요소를 빠르게 찾습니다. n 집단. 이것은 무작위 배정, 우리는 최악의 사례를 계산합니다 예상되는 시간을 실행.

알고리즘은 다음과 같습니다.

QuickSelect(A, k)
  let r be chosen uniformly at random in the range 1 to length(A)
  let pivot = A[r]
  let A1, A2 be new arrays
  # split into a pile A1 of small elements and A2 of big elements
  for i = 1 to n
    if A[i] < pivot then
      append A[i] to A1
    else if A[i] > pivot then
      append A[i] to A2
    else
      # do nothing
  end for
  if k <= length(A1):
    # it's in the pile of small elements
    return QuickSelect(A1, k)
  else if k > length(A) - length(A2)
    # it's in the pile of big elements
    return QuickSelect(A2, k - (length(A) - length(A2))
  else
    # it's equal to the pivot
    return pivot

이 알고리즘의 실행 시간은 얼마입니까? 적대가 우리를 위해 코인을 뒤집는다면, 우리는 피벗이 항상 가장 큰 요소이며 k 항상 1이며, 달리기 시간을 제공합니다

T(n) = Theta(n) + T(n-1) = Theta(n2)

그러나 선택이 실제로 무작위 인 경우 예상되는 실행 시간은

T(n) <= Theta(n) + (1/n) ∑i = 1 ~ nT(max(i, n-i-1))

우리가 재귀가 항상 더 큰 사람에 착륙한다는 전적으로 합리적인 가정을하지 않는 곳 A1 또는 A2.

추측합시다 T(n) <= an 일부 a. 그런 다음 우리는 얻습니다

T(n) 
 <= cn + (1/n) ∑i = 1 ~ nT(max(i-1, n-i))
 = cn + (1/n) ∑i = 1에서 바닥 (N/2) T(n-i) + (1/n) ∑i = 바닥 (n/2) +1 ~ n T(i)
 <= cn + 2 (1/n) ∑i = 바닥 (n/2) ~ n T(i)
 <= cn + 2 (1/n) ∑i = 바닥 (n/2) ~ n ai

그리고 이제 어떻게 든 우리는 플러스 부호의 오른쪽에 끔찍한 금액을 가져와 cn 왼쪽에. 우리가 방금 그것을 묶었다면 2(1/n) ∑i = n/2 ~ n an, 우리는 대략적으로 얻습니다 2(1/n)(n/2)an = an. 그러나 이것은 너무 큽니다 - 추가로 짜낼 여지가 없습니다. cn. 따라서 산술 시리즈 공식을 사용하여 합계를 확장하겠습니다.

∑i = 바닥 (n/2) ~ n i  
 = ∑i = 1 ~ n i - ∑i = 1에서 바닥 (N/2) i  
 = n(n+1)/2 - floor(n/2)(floor(n/2)+1)/2  
 <= n2/2 - (n/4)2/2  
 = (15/32)n2

우리가 못생긴을 대체하기 위해 N을 "충분히 큰"이용하는 곳 floor(n/2) 훨씬 깨끗하고 작은 요소 n/4. 이제 우리는 계속할 수 있습니다

cn + 2 (1/n) ∑i = 바닥 (n/2) ~ n ai,
 <= cn + (2a/n) (15/32) n2
 = n (c + (15/16)a)
 <= an

제공 a > 16c.

이것은 제공합니다 T(n) = O(n). 분명합니다 Omega(n), 우리는 얻습니다 T(n) = Theta(n).

Answer 3

그 ( 'kth liggest element array')에 대한 빠른 Google이 다음을 반환했습니다. http://discuss.joelonsoftware.com/default.asp?interview.11.509587.17

"Make one pass through tracking the three largest values so far." 

(특별히 3D를위한 것이 었습니다)

그리고이 답변 :

Build a heap/priority queue.  O(n)
Pop top element.  O(log n)
Pop top element.  O(log n)
Pop top element.  O(log n)

Total = O(n) + 3 O(log n) = O(n)

Answer 4

당신은 QuickSort를 좋아합니다. 무작위로 요소를 선택하고 모든 것을 높거나 낮게 밀어 넣으십시오. 이 시점에서 실제로 선택한 요소를 알 수 있으며 KTH 요소라면, 그렇지 않으면 kth 요소가 떨어질 것입니다. 통계적으로 말하면, 시간은 시간이 걸립니다. KTH 요소가 N, O (N)으로 자라는 것을 발견하는 데 걸립니다.

Answer 5

알고리즘 분석의 프로그래머 동반자 버전을 제공합니다 ~이다 O (n), 저자는 상수 요인이 너무 높다고 말하지만 순진한 분류 목록-선택 방법을 선호 할 것입니다.

나는 당신의 질문의 편지에 대답했습니다 :)

Answer 6

C ++ 표준 라이브러리는 거의 정확히 있습니다 기능 전화 nth_element, 데이터를 수정하지만. 선형 런 타임, O (n)을 예상했으며 부분적으로도 수행합니다.

const int N = ...;
double a[N];
// ... 
const int m = ...; // m < N
nth_element (a, a + m, a + N);
// a[m] contains the mth element in a

Answer 7

O (n) 복잡성에 대해서는 확실하지 않지만 O (N)과 Nlog (N) 사이에 있어야합니다. 또한 nlog (n)보다 O (n)에 더 가깝게해야합니다. 기능은 Java로 작성됩니다

public int quickSelect(ArrayList<Integer>list, int nthSmallest){
    //Choose random number in range of 0 to array length
    Random random =  new Random();
    //This will give random number which is not greater than length - 1
    int pivotIndex = random.nextInt(list.size() - 1); 

    int pivot = list.get(pivotIndex);

    ArrayList<Integer> smallerNumberList = new ArrayList<Integer>();
    ArrayList<Integer> greaterNumberList = new ArrayList<Integer>();

    //Split list into two. 
    //Value smaller than pivot should go to smallerNumberList
    //Value greater than pivot should go to greaterNumberList
    //Do nothing for value which is equal to pivot
    for(int i=0; i<list.size(); i++){
        if(list.get(i)<pivot){
            smallerNumberList.add(list.get(i));
        }
        else if(list.get(i)>pivot){
            greaterNumberList.add(list.get(i));
        }
        else{
            //Do nothing
        }
    }

    //If smallerNumberList size is greater than nthSmallest value, nthSmallest number must be in this list 
    if(nthSmallest < smallerNumberList.size()){
        return quickSelect(smallerNumberList, nthSmallest);
    }
    //If nthSmallest is greater than [ list.size() - greaterNumberList.size() ], nthSmallest number must be in this list
    //The step is bit tricky. If confusing, please see the above loop once again for clarification.
    else if(nthSmallest > (list.size() - greaterNumberList.size())){
        //nthSmallest will have to be changed here. [ list.size() - greaterNumberList.size() ] elements are already in 
        //smallerNumberList
        nthSmallest = nthSmallest - (list.size() - greaterNumberList.size());
        return quickSelect(greaterNumberList,nthSmallest);
    }
    else{
        return pivot;
    }
}

Answer 8

동적 프로그래밍, 특히 토너먼트 방법을 사용하여 N 분류되지 않은 요소에서 최소를 찾는 것을 구현했습니다. 실행 시간은 O (n + klog (n))입니다. 사용 된 메커니즘은 위키 백과 페이지의 선택 알고리즘에 대한 메소드 중 하나로 나열됩니다 (위의 게시물 중 하나에 표시된 바와 같이). 내 블로그 페이지에서 알고리즘에 대해 읽고 코드 (Java)도 찾을 수 있습니다. 최소 KTH 찾기. 또한 논리는 O (klog (n)) 시간에서 목록을 부분 순서 - 첫 k min (또는 max)을 반환 할 수 있습니다.

코드는 결과 KTH 최소값을 제공했지만 유사한 논리를 사용하여 O (Klog (n))에서 Kth 최대 값을 찾을 수 있으며 토너먼트 트리를 만들기 위해 수행 한 사전 작업을 무시합니다.

Answer 9

당신은 당신이 본 가장 큰 요소를 추적하여 시간 동안 o (n + kn) = o (n) (상수 k)와 공간의 경우 O (k)로 할 수 있습니다.

배열의 각 요소에 대해 가장 큰 k 목록을 스캔하고 가장 작은 요소를 더 큰 경우 새 요소로 교체 할 수 있습니다.

워렌의 우선 힙 솔루션은 깔끔합니다.

Answer 10

Python에서 섹시한 QuickSelect

def quickselect(arr, k):
    '''
     k = 1 returns first element in ascending order.
     can be easily modified to return first element in descending order
    '''

    r = random.randrange(0, len(arr))

    a1 = [i for i in arr if i < arr[r]] '''partition'''
    a2 = [i for i in arr if i > arr[r]]

    if k <= len(a1):
        return quickselect(a1, k)
    elif k > len(arr)-len(a2):
        return quickselect(a2, k - (len(arr) - len(a2)))
    else:
        return arr[r]

Answer 11

선형 시간에 배열의 중앙값을 찾은 다음 QuickSort에서 정확히 파티션 절차를 사용하여 배열을 두 부분으로 나눕니다. , 그 역시 선형 시간에 수행 할 수 있습니다. 이제 kth 요소가있는 배열의 일부로 이동하면 이제 재발이 다음과 같습니다.

Answer 12

아래는 분류되지 않은 알고리즘에서 KTH 요소를 찾기위한 알고리즘이 어떻게 작동하는지에 대한 광범위한 설명으로 전체 구현에 대한 링크입니다. 기본 아이디어는 QuickSort에서와 같이 배열을 분할하는 것입니다. 그러나 극단적 인 사례를 피하기 위해 (예 : 모든 단계에서 가장 작은 요소가 피벗으로 선택 될 때의 알고리즘이 O (n^2) 실행 시간으로 변성되도록하는 경우, Median-of-Medians 알고리즘이라고하는 특수 피벗 선택이 적용됩니다. 전체 솔루션은 O (N) 시간으로 최악의 경우 및 평균 경우에 실행됩니다.

다음은 전체 기사에 대한 링크입니다 (Kth 찾기에 관한 것입니다. 가장 작은 요소이지만 원리는 Kth를 찾는 데 동일합니다. 가장 큰):

분류되지 않은 배열에서 가장 작은 요소 찾기

Answer 13

이 논문에 따라 N 항목 목록에서 가장 큰 항목 찾기 다음 알고리즘이 소요됩니다 O(n) 최악의 경우 시간.

1. 배열을 각각 5 개의 요소의 N/5 목록으로 나눕니다.
2. 5 개의 요소의 각 하위 배열에서 중앙값을 찾으십시오.
3. 모든 중앙값의 중앙값을 재귀 적으로 찾아서 M이라고 부릅니다.
4. 분할 배열에 배열이 두 개의 서브 어레이 1st 하위 배열로 M보다 큰 요소를 포함하고,이 서브 어레이가 A1이라고 가정하고, 다른 서브 어레이에는 M보다 작은 요소가 포함되어 있다고 가정 해 봅시다.
5. k <= | a1 | 인 경우, 선택 (a1, k).
6. k -1 = | a1 | 인 경우, M.
7. k> | a1 | + 1, 반환 선택 (a2, k -a1-1).

분석: 원래 논문에서 제안한대로 :

우리는 중앙값을 사용하여 목록을 두 개의 반쪽으로 분할합니다 (상반기, k <= n/2 , 그리고 후반은 그렇지 않으면). 이 알고리즘에는 시간이 걸립니다 cn 일부 상수에 대한 첫 번째 수준에서 c, cn/2 다음 단계 (크기 N/2 목록에서 되풀이되기 때문에) cn/4 세 번째 수준에서. 총 시간은입니다 cn + cn/2 + cn/4 + .... = 2cn = o(n).

파티션 크기가 3이 아닌 5 개를 촬영하는 이유는 무엇입니까?

원본에서 언급했듯이 종이:

목록을 5로 나누면 70-30의 최악의 분할이 보장됩니다. 중앙값의 중앙값의 절반은 중앙값보다 큰 중앙값의 절반이므로 N/5 블록의 적어도 절반은 3 개의 요소를 가지고 있으며 이는 다음과 같습니다. 3n/10 스플릿은 다른 파티션이 최악의 경우 7N/10이라는 것을 의미합니다. 그게 주어집니다 T(n) = T(n/5)+T(7n/10)+O(n). Since n/5+7n/10 < 1, 최악의 실행 시간은입니다O(n).

이제 위의 알고리즘을 다음과 같이 구현하려고했습니다.

public static int findKthLargestUsingMedian(Integer[] array, int k) {
        // Step 1: Divide the list into n/5 lists of 5 element each.
        int noOfRequiredLists = (int) Math.ceil(array.length / 5.0);
        // Step 2: Find pivotal element aka median of medians.
        int medianOfMedian =  findMedianOfMedians(array, noOfRequiredLists);
        //Now we need two lists split using medianOfMedian as pivot. All elements in list listOne will be grater than medianOfMedian and listTwo will have elements lesser than medianOfMedian.
        List<Integer> listWithGreaterNumbers = new ArrayList<>(); // elements greater than medianOfMedian
        List<Integer> listWithSmallerNumbers = new ArrayList<>(); // elements less than medianOfMedian
        for (Integer element : array) {
            if (element < medianOfMedian) {
                listWithSmallerNumbers.add(element);
            } else if (element > medianOfMedian) {
                listWithGreaterNumbers.add(element);
            }
        }
        // Next step.
        if (k <= listWithGreaterNumbers.size()) return findKthLargestUsingMedian((Integer[]) listWithGreaterNumbers.toArray(new Integer[listWithGreaterNumbers.size()]), k);
        else if ((k - 1) == listWithGreaterNumbers.size()) return medianOfMedian;
        else if (k > (listWithGreaterNumbers.size() + 1)) return findKthLargestUsingMedian((Integer[]) listWithSmallerNumbers.toArray(new Integer[listWithSmallerNumbers.size()]), k-listWithGreaterNumbers.size()-1);
        return -1;
    }

    public static int findMedianOfMedians(Integer[] mainList, int noOfRequiredLists) {
        int[] medians = new int[noOfRequiredLists];
        for (int count = 0; count < noOfRequiredLists; count++) {
            int startOfPartialArray = 5 * count;
            int endOfPartialArray = startOfPartialArray + 5;
            Integer[] partialArray = Arrays.copyOfRange((Integer[]) mainList, startOfPartialArray, endOfPartialArray);
            // Step 2: Find median of each of these sublists.
            int medianIndex = partialArray.length/2;
            medians[count] = partialArray[medianIndex];
        }
        // Step 3: Find median of the medians.
        return medians[medians.length / 2];
    }

완료를 위해 다른 알고리즘은 우선 순위 대기열을 사용하고 시간이 걸립니다. O(nlogn).

public static int findKthLargestUsingPriorityQueue(Integer[] nums, int k) {
        int p = 0;
        int numElements = nums.length;
        // create priority queue where all the elements of nums will be stored
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>();

        // place all the elements of the array to this priority queue
        for (int n : nums) {
            pq.add(n);
        }

        // extract the kth largest element
        while (numElements - k + 1 > 0) {
            p = pq.poll();
            k++;
        }

        return p;
    }

이 알고리즘은 모두 다음과 같이 테스트 할 수 있습니다.

public static void main(String[] args) throws IOException {
        Integer[] numbers = new Integer[]{2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};
        System.out.println(findKthLargestUsingMedian(numbers, 8));
        System.out.println(findKthLargestUsingPriorityQueue(numbers, 8));
    }

예상 출력은 다음과 같습니다.18 18

Answer 14

이런다는 접근 방식은 어떻습니까

a buffer of length k 그리고 a tmp_max, tmp_max를 얻는 것은 O (k)이며 n 번으로 완료됩니다. O(kn)

옳거나 내가 뭔가 빠졌나요?

비록 QuickSelect의 평균 사례와 최악의 중간 통계 방법을 이길 수는 없지만 이해하고 구현하기가 매우 쉽습니다.

Answer 15

목록을 반복하십시오. 현재 값이 저장된 가장 큰 값보다 큰 경우 가장 큰 값으로 저장하고 1-4로 낮추고 5가 목록에서 떨어집니다. 그렇지 않다면 2 번과 비교하고 같은 일을하십시오. 5 개의 저장된 값에 대해 확인하고 반복하십시오. 이것은 O (n)에서해야합니다.

Answer 16

한 가지 대답을 제안하고 싶습니다

첫 번째 k 요소를 가져 와서 링크 된 k 값 목록으로 분류하는 경우

최악의 경우에도 삽입 NK 값에 대해 삽입 정렬을 수행하는 경우 최악의 경우에도 다른 모든 값에 대해 이제 K*(NK)이고 정렬되는 이전 K 값은 K*(k- 1) 그래서 그것은 O (n) 인 (NK-K)로 나옵니다.

건배

Answer 17

N 중에서 가장 큰 정수를 찾기위한 중앙값 -Medians 알고리즘에 대한 설명은 여기에서 찾을 수 있습니다.http://cs.indstate.edu/~spitla/presentation.pdf

C ++의 구현은 다음과 같습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int findMedian(vector<int> vec){
//    Find median of a vector
    int median;
    size_t size = vec.size();
    median = vec[(size/2)];
    return median;
}

int findMedianOfMedians(vector<vector<int> > values){
    vector<int> medians;

    for (int i = 0; i < values.size(); i++) {
        int m = findMedian(values[i]);
        medians.push_back(m);
    }

    return findMedian(medians);
}

void selectionByMedianOfMedians(const vector<int> values, int k){
//    Divide the list into n/5 lists of 5 elements each
    vector<vector<int> > vec2D;

    int count = 0;
    while (count != values.size()) {
        int countRow = 0;
        vector<int> row;

        while ((countRow < 5) && (count < values.size())) {
            row.push_back(values[count]);
            count++;
            countRow++;
        }
        vec2D.push_back(row);
    }

    cout<<endl<<endl<<"Printing 2D vector : "<<endl;
    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            cout<<vec2D[i][j]<<" ";
        }
        cout<<endl;
    }
    cout<<endl;

//    Calculating a new pivot for making splits
    int m = findMedianOfMedians(vec2D);
    cout<<"Median of medians is : "<<m<<endl;

//    Partition the list into unique elements larger than 'm' (call this sublist L1) and
//    those smaller them 'm' (call this sublist L2)
    vector<int> L1, L2;

    for (int i = 0; i < vec2D.size(); i++) {
        for (int j = 0; j < vec2D[i].size(); j++) {
            if (vec2D[i][j] > m) {
                L1.push_back(vec2D[i][j]);
            }else if (vec2D[i][j] < m){
                L2.push_back(vec2D[i][j]);
            }
        }
    }

//    Checking the splits as per the new pivot 'm'
    cout<<endl<<"Printing L1 : "<<endl;
    for (int i = 0; i < L1.size(); i++) {
        cout<<L1[i]<<" ";
    }

    cout<<endl<<endl<<"Printing L2 : "<<endl;
    for (int i = 0; i < L2.size(); i++) {
        cout<<L2[i]<<" ";
    }

//    Recursive calls
    if ((k - 1) == L1.size()) {
        cout<<endl<<endl<<"Answer :"<<m;
    }else if (k <= L1.size()) {
        return selectionByMedianOfMedians(L1, k);
    }else if (k > (L1.size() + 1)){
        return selectionByMedianOfMedians(L2, k-((int)L1.size())-1);
    }

}

int main()
{
    int values[] = {2, 3, 5, 4, 1, 12, 11, 13, 16, 7, 8, 6, 10, 9, 17, 15, 19, 20, 18, 23, 21, 22, 25, 24, 14};

    vector<int> vec(values, values + 25);

    cout<<"The given array is : "<<endl;
    for (int i = 0; i < vec.size(); i++) {
        cout<<vec[i]<<" ";
    }

    selectionByMedianOfMedians(vec, 8);

    return 0;
}

Answer 18

도 있습니다 Wirth의 선택 알고리즘, QuickSelect보다 더 간단한 구현이 있습니다. WIRTH의 선택 알고리즘은 QuickSelect보다 느리지 만 약간의 개선으로 인해 더 빠릅니다.

더 자세하게. Vladimir Zabrodsky의 Modifind 최적화와 3 개의 중앙 피벗 선택을 사용하고 알고리즘의 파티셔닝 부분의 마지막 단계에주의를 기울여 다음 알고리즘 (상상할 수있는 "Lefselect")을 생각해 냈습니다.

#define F_SWAP(a,b) { float temp=(a);(a)=(b);(b)=temp; }

# Note: The code needs more than 2 elements to work
float lefselect(float a[], const int n, const int k) {
    int l=0, m = n-1, i=l, j=m;
    float x;

    while (l<m) {
        if( a[k] < a[i] ) F_SWAP(a[i],a[k]);
        if( a[j] < a[i] ) F_SWAP(a[i],a[j]);
        if( a[j] < a[k] ) F_SWAP(a[k],a[j]);

        x=a[k];
        while (j>k & i<k) {
            do i++; while (a[i]<x);
            do j--; while (a[j]>x);

            F_SWAP(a[i],a[j]);
        }
        i++; j--;

        if (j<k) {
            while (a[i]<x) i++;
            l=i; j=m;
        }
        if (k<i) {
            while (x<a[j]) j--;
            m=j; i=l;
        }
    }
    return a[k];
}

내가 한 벤치 마크에서 여기, lefselect는 QuickSelect보다 20-30% 빠릅니다.

Answer 19

Haskell 솔루션 :

kthElem index list = sort list !! index

withShape ~[]     []     = []
withShape ~(x:xs) (y:ys) = x : withShape xs ys

sort []     = []
sort (x:xs) = (sort ls `withShape` ls) ++ [x] ++ (sort rs `withShape` rs)
  where
   ls = filter (<  x)
   rs = filter (>= x)

이것은 WithShape 방법을 사용하여 실제로 계산하지 않고 파티션의 크기를 발견함으로써 중간 솔루션의 중앙값을 구현합니다.

Answer 20

다음은 Randomized QuickSelect의 C++ 구현입니다.아이디어는 피벗 요소를 무작위로 선택하는 것입니다.무작위 분할을 구현하기 위해 무작위 함수 rand()를 사용하여 l과 r 사이의 인덱스를 생성하고 무작위로 생성된 인덱스의 요소를 마지막 요소와 교환한 다음 마지막 요소를 피벗으로 사용하는 표준 파티션 프로세스를 호출합니다.

#include<iostream>
#include<climits>
#include<cstdlib>
using namespace std;

int randomPartition(int arr[], int l, int r);

// This function returns k'th smallest element in arr[l..r] using
// QuickSort based method.  ASSUMPTION: ALL ELEMENTS IN ARR[] ARE DISTINCT
int kthSmallest(int arr[], int l, int r, int k)
{
    // If k is smaller than number of elements in array
    if (k > 0 && k <= r - l + 1)
    {
        // Partition the array around a random element and
        // get position of pivot element in sorted array
        int pos = randomPartition(arr, l, r);

        // If position is same as k
        if (pos-l == k-1)
            return arr[pos];
        if (pos-l > k-1)  // If position is more, recur for left subarray
            return kthSmallest(arr, l, pos-1, k);

        // Else recur for right subarray
        return kthSmallest(arr, pos+1, r, k-pos+l-1);
    }

    // If k is more than number of elements in array
    return INT_MAX;
}

void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

// Standard partition process of QuickSort().  It considers the last
// element as pivot and moves all smaller element to left of it and
// greater elements to right. This function is used by randomPartition()
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++)
    {
        if (arr[j] <= x) //arr[i] is bigger than arr[j] so swap them
        {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }
    swap(&arr[i], &arr[r]); // swap the pivot
    return i;
}

// Picks a random pivot element between l and r and partitions
// arr[l..r] around the randomly picked element using partition()
int randomPartition(int arr[], int l, int r)
{
    int n = r-l+1;
    int pivot = rand() % n;
    swap(&arr[l + pivot], &arr[r]);
    return partition(arr, l, r);
}

// Driver program to test above methods
int main()
{
    int arr[] = {12, 3, 5, 7, 4, 19, 26};
    int n = sizeof(arr)/sizeof(arr[0]), k = 3;
    cout << "K'th smallest element is " << kthSmallest(arr, 0, n-1, k);
    return 0;
}

위 솔루션의 최악의 경우 시간 복잡도는 여전히 O(n2)입니다. 최악의 경우 무작위 함수는 항상 모서리 요소를 선택할 수 있습니다.위의 무작위 QuickSelect의 예상 시간 복잡도는 Θ(n)입니다.

Answer 21

1. 우선순위 대기열이 생성되었습니다.
2. 모든 요소를 ​​힙에 삽입합니다.

3. poll()을 k번 호출합니다.

   public static int getKthLargestElements(int[] arr)
   {
       PriorityQueue<Integer> pq =  new PriorityQueue<>((x , y) -> (y-x));
       //insert all the elements into heap
       for(int ele : arr)
          pq.offer(ele);
       // call poll() k times
       int i=0;
       while(i&lt;k)
        {
          int result = pq.poll();
        } 
      return result;        
   }
   

Answer 22

이것은 JavaScript의 구현입니다.

배열을 수정할 수 없다는 제약 조건을 해제하면 두 인덱스를 사용하여 추가 메모리를 사용하여 "현재 파티션"(클래식 QuickSort 스타일로 -)를 식별 할 수 있습니다. http://www.nczonline.net/blog/2012/11/27/computer-science-in-javascript-quicksort/).

function kthMax(a, k){
    var size = a.length;

    var pivot = a[ parseInt(Math.random()*size) ]; //Another choice could have been (size / 2) 

    //Create an array with all element lower than the pivot and an array with all element higher than the pivot
    var i, lowerArray = [], upperArray = [];
    for (i = 0; i  < size; i++){
        var current = a[i];

        if (current < pivot) {
            lowerArray.push(current);
        } else if (current > pivot) {
            upperArray.push(current);
        }
    }

    //Which one should I continue with?
    if(k <= upperArray.length) {
        //Upper
        return kthMax(upperArray, k);
    } else {
        var newK = k - (size - lowerArray.length);

        if (newK > 0) {
            ///Lower
            return kthMax(lowerArray, newK);
        } else {
            //None ... it's the current pivot!
            return pivot;
        }   
    }
}  

작동 방식을 테스트하려면이 변형을 사용할 수 있습니다.

    function kthMax (a, k, logging) {
         var comparisonCount = 0; //Number of comparison that the algorithm uses
         var memoryCount = 0;     //Number of integers in memory that the algorithm uses
         var _log = logging;

         if(k < 0 || k >= a.length) {
            if (_log) console.log ("k is out of range"); 
            return false;
         }      

         function _kthmax(a, k){
             var size = a.length;
             var pivot = a[parseInt(Math.random()*size)];
             if(_log) console.log("Inputs:", a,  "size="+size, "k="+k, "pivot="+pivot);

             // This should never happen. Just a nice check in this exercise
             // if you are playing with the code to avoid never ending recursion            
             if(typeof pivot === "undefined") {
                 if (_log) console.log ("Ops..."); 
                 return false;
             }

             var i, lowerArray = [], upperArray = [];
             for (i = 0; i  < size; i++){
                 var current = a[i];
                 if (current < pivot) {
                     comparisonCount += 1;
                     memoryCount++;
                     lowerArray.push(current);
                 } else if (current > pivot) {
                     comparisonCount += 2;
                     memoryCount++;
                     upperArray.push(current);
                 }
             }
             if(_log) console.log("Pivoting:",lowerArray, "*"+pivot+"*", upperArray);

             if(k <= upperArray.length) {
                 comparisonCount += 1;
                 return _kthmax(upperArray, k);
             } else if (k > size - lowerArray.length) {
                 comparisonCount += 2;
                 return _kthmax(lowerArray, k - (size - lowerArray.length));
             } else {
                 comparisonCount += 2;
                 return pivot;
             }
     /* 
      * BTW, this is the logic for kthMin if we want to implement that... ;-)
      * 

             if(k <= lowerArray.length) {
                 return kthMin(lowerArray, k);
             } else if (k > size - upperArray.length) {
                 return kthMin(upperArray, k - (size - upperArray.length));
             } else 
                 return pivot;
     */            
         }

         var result = _kthmax(a, k);
         return {result: result, iterations: comparisonCount, memory: memoryCount};
     }

코드의 나머지 부분은 단지 놀이터를 만드는 것입니다.

    function getRandomArray (n){
        var ar = [];
        for (var i = 0, l = n; i < l; i++) {
            ar.push(Math.round(Math.random() * l))
        }

        return ar;
    }

    //Create a random array of 50 numbers
    var ar = getRandomArray (50);   

이제 몇 번 테스트합니다. Math.random () 때문에 다른 결과를 얻을 때마다 생성됩니다.

    kthMax(ar, 2, true);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 2);
    kthMax(ar, 34, true);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);
    kthMax(ar, 34);

몇 번 테스트하면 반복 횟수가 평균적으로 o (n) ~ = 상수 * n이고 k의 값은 알고리즘에 영향을 미치지 않는다는 것을 경험적으로 볼 수 있습니다.

Answer 23

나는이 알고리즘을 생각해 냈고 o (n) 인 것 같습니다.

K = 3이라고 가정하고 배열에서 세 번째로 큰 항목을 찾고 싶습니다. 세 가지 변수를 생성하고 배열의 각 항목을이 세 가지 변수의 최소값과 비교합니다. 배열 항목이 최소보다 크면 최소 변수를 항목 값으로 바꿉니다. 우리는 배열 끝까지 같은 것을 계속합니다. 세 가지 변수의 최소값은 배열에서 세 번째로 큰 항목입니다.

define variables a=0, b=0, c=0
iterate through the array items
    find minimum a,b,c
    if item > min then replace the min variable with item value
    continue until end of array
the minimum of a,b,c is our answer

그리고 Kth 가장 큰 항목을 찾으려면 K 변수가 필요합니다.

예 : (k = 3)

[1,2,4,1,7,3,9,5,6,2,9,8]

Final variable values:

a=7 (answer)
b=8
c=9

누군가 이것을 검토하고 내가 누락 된 것을 알려줄 수 있습니까?

Answer 24

다음은 Eladv가 제안한 알고리즘의 구현입니다 (나는 또한 임의의 피벗으로 구현을 여기에 두었습니다).

public class Median {

    public static void main(String[] s) {

        int[] test = {4,18,20,3,7,13,5,8,2,1,15,17,25,30,16};
        System.out.println(selectK(test,8));

        /*
        int n = 100000000;
        int[] test = new int[n];
        for(int i=0; i<test.length; i++)
            test[i] = (int)(Math.random()*test.length);

        long start = System.currentTimeMillis();
        random_selectK(test, test.length/2);
        long end = System.currentTimeMillis();
        System.out.println(end - start);
        */
    }

    public static int random_selectK(int[] a, int k) {
        if(a.length <= 1)
            return a[0];

        int r = (int)(Math.random() * a.length);
        int p = a[r];

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return random_selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return random_selectK(temp,k-small-equal);
        }
    }

    public static int selectK(int[] a, int k) {
        if(a.length <= 5) {
            Arrays.sort(a);
            return a[k-1];
        }

        int p = median_of_medians(a);

        int small = 0, equal = 0, big = 0;
        for(int i=0; i<a.length; i++) {
            if(a[i] < p) small++;
            else if(a[i] == p) equal++;
            else if(a[i] > p) big++;
        }

        if(k <= small) {
            int[] temp = new int[small];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] < p)
                    temp[j++] = a[i];
            return selectK(temp, k);
        }

        else if (k <= small+equal)
            return p;

        else {
            int[] temp = new int[big];
            for(int i=0, j=0; i<a.length; i++)
                if(a[i] > p)
                    temp[j++] = a[i];
            return selectK(temp,k-small-equal);
        }
    }

    private static int median_of_medians(int[] a) {
        int[] b = new int[a.length/5];
        int[] temp = new int[5];
        for(int i=0; i<b.length; i++) {
            for(int j=0; j<5; j++)
                temp[j] = a[5*i + j];
            Arrays.sort(temp);
            b[i] = temp[2];
        }

        return selectK(b, b.length/2 + 1);
    }
}

Answer 25

그것은 우리가 임의의 피벗을 선택하고 작은 요소를 왼쪽으로 가져오고 오른쪽으로 더 큰 QuickSort 전략과 유사합니다.

    public static int kthElInUnsortedList(List<int> list, int k)
    {
        if (list.Count == 1)
            return list[0];

        List<int> left = new List<int>();
        List<int> right = new List<int>();

        int pivotIndex = list.Count / 2;
        int pivot = list[pivotIndex]; //arbitrary

        for (int i = 0; i < list.Count && i != pivotIndex; i++)
        {
            int currentEl = list[i];
            if (currentEl < pivot)
                left.Add(currentEl);
            else
                right.Add(currentEl);
        }

        if (k == left.Count + 1)
            return pivot;

        if (left.Count < k)
            return kthElInUnsortedList(right, k - left.Count - 1);
        else
            return kthElInUnsortedList(left, k);
    }

Answer 26

이 링크의 끝으로 이동하십시오 : ...........

http://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array-set-3-worst-case-lineartime/

Answer 27

O (n) 시간과 일정한 공간에서 가장 작은 요소를 찾을 수 있습니다. 배열이 정수만을 고려하는 경우.

접근 방식은 배열 값 범위에서 이진 검색을 수행하는 것입니다. 정수 범위에 Min_Value와 Max_Value가있는 경우 해당 범위에서 이진 검색을 수행 할 수 있습니다. 우리는 어떤 값이 kth-smallest 또는 kth-smallest보다 kth-smallest 또는 더 작은지 알려주는 비교 기능을 작성할 수 있습니다. Kth-Smallest 번호에 도달 할 때까지 이진 검색을 수행하십시오.

다음은 코드입니다

수업 솔루션 :

def _iskthsmallest(self, A, val, k):
    less_count, equal_count = 0, 0
    for i in range(len(A)):
        if A[i] == val: equal_count += 1
        if A[i] < val: less_count += 1

    if less_count >= k: return 1
    if less_count + equal_count < k: return -1
    return 0

def kthsmallest_binary(self, A, min_val, max_val, k):
    if min_val == max_val:
        return min_val
    mid = (min_val + max_val)/2
    iskthsmallest = self._iskthsmallest(A, mid, k)
    if iskthsmallest == 0: return mid
    if iskthsmallest > 0: return self.kthsmallest_binary(A, min_val, mid, k)
    return self.kthsmallest_binary(A, mid+1, max_val, k)

# @param A : tuple of integers
# @param B : integer
# @return an integer
def kthsmallest(self, A, k):
    if not A: return 0
    if k > len(A): return 0
    min_val, max_val = min(A), max(A)
    return self.kthsmallest_binary(A, min_val, max_val, k)

Answer 28

QuickSelect 알고리즘을 능가하는 알고리즘이 하나 있습니다. 라고 불린다 Floyd-Rivets (FR) 알고리즘.

원본 기사 : https://doi.org/10.1145/360680.360694

다운로드 가능한 버전 : http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.309.7108&rep=rep1&type=pdf

위키 백과 기사 https://en.wikipedia.org/wiki/floyd%E2%80%93rivest_algorithm

C ++에서 QuickSelect 및 FR 알고리즘을 구현하려고했습니다. 또한 표준 C ++ 라이브러리 구현 STD :: NTH_ELEMENT (기본적으로 QuickSelect 및 HeapSelect의 내부 선택)와 비교했습니다. 결과는 QuickSelect이고 Nth_Element는 평균적으로 비교적으로 실행되었지만 FR 알고리즘은 약을 기록했습니다. 그들에 비해 두 배 빠른.

FR 알고리즘에 사용한 샘플 코드 :

template <typename T>
T FRselect(std::vector<T>& data, const size_t& n)
{
    if (n == 0)
        return *(std::min_element(data.begin(), data.end()));
    else if (n == data.size() - 1)
        return *(std::max_element(data.begin(), data.end()));
    else
        return _FRselect(data, 0, data.size() - 1, n);
}

template <typename T>
T _FRselect(std::vector<T>& data, const size_t& left, const size_t& right, const size_t& n)
{
    size_t leftIdx = left;
    size_t rightIdx = right;

    while (rightIdx > leftIdx)
    {
        if (rightIdx - leftIdx > 600)
        {
            size_t range = rightIdx - leftIdx + 1;
            long long i = n - (long long)leftIdx + 1;
            long long z = log(range);
            long long s = 0.5 * exp(2 * z / 3);
            long long sd = 0.5 * sqrt(z * s * (range - s) / range) * sgn(i - (long long)range / 2);

            size_t newLeft = fmax(leftIdx, n - i * s / range + sd);
            size_t newRight = fmin(rightIdx, n + (range - i) * s / range + sd);

            _FRselect(data, newLeft, newRight, n);
        }
        T t = data[n];
        size_t i = leftIdx;
        size_t j = rightIdx;
        // arrange pivot and right index
        std::swap(data[leftIdx], data[n]);
        if (data[rightIdx] > t)
            std::swap(data[rightIdx], data[leftIdx]);

        while (i < j)
        {
            std::swap(data[i], data[j]);
            ++i; --j;
            while (data[i] < t) ++i;
            while (data[j] > t) --j;
        }

        if (data[leftIdx] == t)
            std::swap(data[leftIdx], data[j]);
        else
        {
            ++j;
            std::swap(data[j], data[rightIdx]);
        }
        // adjust left and right towards the boundaries of the subset
        // containing the (k - left + 1)th smallest element
        if (j <= n)
            leftIdx = j + 1;
        if (n <= j)
            rightIdx = j - 1;
    }

    return data[leftIdx];
}

template <typename T>
int sgn(T val) {
    return (T(0) < val) - (val < T(0));
}

Answer 29

내가 할 일은 이것입니다 :

initialize empty doubly linked list l
for each element e in array
    if e larger than head(l)
        make e the new head of l
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

링크 된 목록의 첫 번째 및 마지막 요소에 포인터를 저장할 수 있습니다. 목록에 대한 업데이트가있을 때만 변경됩니다.

업데이트:

initialize empty sorted tree l
for each element e in array
    if e between head(l) and tail(l)
        insert e into l // O(log k)
        if size(l) > k
            remove last element from l

the last element of l should now be the kth largest element

Answer 30

먼저 O (n) 시간이 걸리고 BST에서 BST를 구축 할 수 있으며 BST에서 O (log (n))에서 가장 작은 요소를 찾을 수있는 모든 수 (O (n) 순서까지.