Top K问题——Parition算法

Top K问题概述

• 在非海量数据的情况下，Top K问题的首推解法就是快排中的Parition算法。不仅平均时间复杂度优越，可以达到O(n)，并且相比于基于堆的算法（包括：min_heapify、build_heap、insert等一系列过程），编码更简洁。
• 在海量数据的情况下，还是老老实实选择基于堆的这一数据结构的算法吧。时间复杂度为O(nlogk)。并且大多数高级编程语言中都应该内置了基于堆的API，所以编写起来也没有那么麻烦，例如JDK中的：java.util.PriorityQueue<>。

基于Partition算法

• 选择一个Position（称为基准），基于该算法的Top k算法，非常受Position好坏的影响，所谓的坏，有可能使时间复杂度达到O(n*n)。
• 然后利用Partition算法进行划分，如果Partition得到的p小于K，则继续划分p的右边，如果p大于K，则继续划分p的左边，如果p等于K，则算法结束。

Code

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;
    }
}