Top K問題——Partionアルゴリズム

Top K問題の概要

は、非多量データの場合、Top K問題の最初の推解は、高速列のPartionアルゴリズムである.平均時間の複雑さに優れるだけでなく、O(n)に達することができ、また、スタックベースのアルゴリズム(minuheaphiy、builduheap、insertなど一連のプロセスを含む)に比べて、符号化はより簡潔である.

海量データの場合は、積み重ねに基づくデータ構造のアルゴリズムを正直に選択しましょう.時間の複雑さはOです.そして、多くの高級プログラミング言語には、ヒープベースのAPIが内蔵されているはずであるので、JDKのjava.util.PriorityQueue<>など、書くのもそれほど面倒ではない.

パーティションアルゴリズムに基づいて

は、Position(基準と呼ばれる)を選択し、アルゴリズムのTop kアルゴリズムに基づいて、Positionの善し悪しの影響を強く受け、時間の複雑さがO(n＊n)に達する可能性がある.

はその後、Partationアルゴリズムを用いて分割し、Partationで得られたpがKより小さい場合、pの右側を分割し続ける.pがKより大きい場合、pの左側を分割し続ける.pがKに等しい場合、アルゴリズムは終了する.

コード

import java.util.Scanner;

/**
 *      parition  ，   k  ，        O(n)
 */
public class FindK
{
    //  
    public static void main(String[] args)
    {
        int k = 0;
        Scanner scanner = new Scanner(System.in);
        k = scanner.nextInt();
        scanner.close();

        int[] a = {2, 6, 3, 10, 45, 12, 5, 6, 5, 6};
        if (k >= 0 && k < a.length) {
            findMaxK(a, 0, a.length - 1, k);
            System.out.println(" "+ (k+1) +"   ：" + a[k]);
        } else
            System.out.println("are you kidding me ?");
    }
    
    //    
    private static void findMaxK(int[] a, int low, int high, int k)
    {
        int p = partition(a, low, high);
        if (p == k)
        {
            return;
        }
        if (p < k)
        {
            findMaxK(a, p + 1, high, k);
        }else{
            findMaxK(a, low, p - 1, k);
        }
    }

    //    ：  
    private static int partition(int[] a, int low, int high)
    {
        int position = a[high];
        int i = low - 1;
        for (int j = low; j < high; ++j)
        {
            if (a[j] <= position)
            {
                ++i;
                exchange(a, i, j);
            }
        }
        exchange(a, i + 1, high);
        return i + 1;
    }

    static void exchange(int[] a, int i, int j)
    {
        int temp = a[j];
        a[j] = a[i];
        a[i] = temp;
    }
}