文档章节

TOP-K问题的几种解法

AbeJeffrey
 AbeJeffrey
发布于 2018/03/12 18:04
字数 2089
阅读 7.4K
收藏 1

解法一

最简单且最容易想到的算法是对数组进行排序(快速排序),然后取最大或最小的K个元素。总的时间复杂度为O(N*logN)+O(K)=O(N*logN)。该算法存在以下问题:

  1. 快速排序的平均复杂度为O(N*logN),但最坏时间复杂度为O(n2),不能始终保证较好的复杂度
  2. 只需要前k大或k小的数,,实际对其余不需要的数也进行了排序,浪费了大量排序时间

总结:通常不会采取该方案。

解法二

虽然我们不会采用快速排序的算法来实现TOP-K问题,但我们可以利用快速排序的思想,在数组中随机找一个元素key,将数组分成两部分Sa和Sb,其中Sa的元素>=key,Sb的元素<key,然后分析两种情况:

  • 若Sa中元素的个数大于或等于k,则在Sa中查找最大的k个数
  • 若Sa中元素的个数小于k,其个数为len,则在Sb中查找k-len个数字

如此递归下去,不断把问题分解为更小的问题,直到求出结果。

该算法的平均时间复杂度为O(N * logk)。以求K大的数为例,算法实现如下:

public static int findTopK(int[] array, int left, int right, int k) {
    int index = -1;
    if (left < right) {
        int pos = partition(array, left, right);
        int len = pos - left + 1;
        if (len == k) {
            index = pos;
        } else if (len < k) {//Sa中元素个数小于K,到Sb中查找k-len个数字
            index = findTopK(array, pos + 1, right, k - len);
        } else {//Sa中元素的个数大于或等于k
            index = findTopK(array, left, pos - 1, k);
        }
    }
    return index;
}

/**
 * 按基准点划分数组,左边的元素大于基准点,右边的元素小于基准点
 *
 * @param array
 * @param left
 * @param right
 * @return
 */
public static int partition(int[] array, int left, int right) {
    int x = array[left];//基准点,随机选择
    do {
        while (array[right] < x && left < right)//从后向前扫描,找到第一个比基准点大的元素
            right--;
        if (left < right) {
            array[left] = array[right];//大元素前移
            left++; 
        }
        while (array[left] >= x && left < right) //从前向后扫描,找到第一个比基准点小的元素
            left++;
        if (left < right) {
            array[right] = array[left];//小元素后移
            right--;
        }
    } while (left < right);
    array[left] = x;
    return left;
}

单元测试:

@Test
public void testFindKMax_1() {
    int k = 4;
    int array[] = {20, 100, 4, 2, 87, 9, 8, 5, 46, 26};
    TopK.findTopK(array, 0, array.length - 1, k);
    logger.info("array top k:{}", Arrays.stream(array).mapToObj(value -> String.valueOf(value))
            .limit(k).collect(Collectors.joining(",")));
}

解法三

寻找N个数中的第K大的数,可以将问题转化寻找N个数中第K大的问题。对于一个给定的数p, 可以在O(N)的时间复杂度内找出所有不小于P的数。

根据分析,可以使用二分查找的算法思想来寻找N个数中第K大的数。假设N个数中最大的数为Vmax,最小的数为Vmin, 那么N个数中第K大的数一定在区间[Vmin,Vmax]之间。然后在这个区间使用二分查找算法。算法实现如下:

public static List<Integer> findTopK(int[] array, int k) {
    int max = array[0];
    int min = array[0];
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
        if (min > array[i]) {
            min = array[i];
        }
    }
    List<Integer> topKList = new ArrayList<>();
    int key = findK(array, max, min, k);
    for (int i = 0; i < array.length; i++) {
        if (array[i] >= key) {
            topKList.add(array[i]);
        }
    }
    return topKList;
}

/**
 * 寻找第K大的元素
 *
 * @param array
 * @param max
 * @param min
 * @param k
 * @return
 */
private static int findK(int[] array, int max, int min, int k) {
    while (max - min > 1) {
        int mid = (max + min) / 2;
        int num = findKNum(array, mid);
        if (num >= k) {
            min = mid;
        } else {
            max = mid;
        }
    }
    return min;
}

/**
 * 统计不小于key的元素个数
 *
 * @param array
 * @param key
 * @return
 */
private static int findKNum(int[] array, int key) {
    int sum = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] >= key)
            sum++;
    }
    return sum;
}

总结:该算法实际应用效果不佳,尤其是不同的数据类型需要确定max - min > delta,因此时间复杂度跟数据分布有关。 整个算法的时间复杂度为O(N * log(Vmax-Vmin)/delta),在数据分布平均的情况下,时间复杂度为O(N * logN)。

解法四

上面几种解法都会对数据访问多次,那么就有一个问题,当数组中元素个数非常大时,如:100亿,这时候数据不能全部加载到内存,就要求我们尽可能少的遍历所有数据。针对这种情况,下面我们介绍一种针对海量数据的解决方案。

在学习堆排序的过程中,我们知道了堆这种数据结构。为了查找Top k大的数,我们可以使用大根堆来存储最大的K个元素。大根堆的堆顶元素就是最大K个数中最小的一个。每次考虑下一个数x时,如果x比堆顶元素小,则不需要改变原来的堆。如果想x比堆顶元素大,那么用x替换堆顶元素, 同时,在替换之后,x可能破坏最小堆的结构,需要调整堆来维持堆的性质。算法实现如下:

public static int[] findTopK(int[] array, int k) {
    int heapArray[] = new int[k];
    for (int i = 0; i < k; i++) {
        heapArray[i] = array[i];
    }
    buildMaxHeap(heapArray);
    for (int i = k; i < array.length; i++) {
        if (array[i] < heapArray[0]) {
            heapArray[0] = array[i];//更新堆顶
            adjustMaxHeap(heapArray, 0, heapArray.length);
        }
    }
    return heapArray;
}
/**
 * 构建大根堆
 *
 * @param array
 */
public static void buildMaxHeap(int[] array) {
    for (int i = array.length / 2 - 1; i >= 0; i--) {
        adjustMaxHeap(array, i, array.length);
    }
}
/**
 * 调整堆结构
 *
 * @param array
 * @param root   根节点
 * @param length
 */
public static void adjustMaxHeap(int[] array, int root, int length) {
    int left = root * 2 + 1; //左节点下标,数组下标从0开始,所以加1
    int right = left + 1; //右节点下标
    int largest = root;// 存放三个节点中最大节点的下标
    if (left < length && array[left] > array[root]) { //左节点大于根节点,更新最大节点的下标
        largest = left;
    }
    if (right < length && array[right] > array[largest]) {//右节点大于根节点,最大节点的下标
        largest = right;
    }
    if (root != largest) {
        swap(array, largest, root);
        adjustMaxHeap(array, largest, length);
    }
}
/**
 * 交换
 *
 * @param arr
 * @param i
 * @param j
 */
public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

总结:该算法只需要扫描所有的数据一次,且不会占用太多内存空间(只需要容纳K个元素的空间),尤其适合处理海量数据的场景。算法的时间复杂度为O(N * logk),这实际上相当于执行了部分堆排序。

扩展:当K仍然很大,导致内存无法容纳K个元素时,我们可以考虑先找最大的K1个元素,然后再找看K1+1到2*K1个元素,如此类推。(其中容量为K1的堆可以完全载入内存)

解法五

TOP-K问题是一个经典的问题,这个问题是存在线性算法的,只不过算法的使用范围有一定的限制。如果所有N个数都是正整数,且他们的取值范围并不大,可以考虑申请空间,记录每个整数出现的次数,然后再从大到小取最大的K个。实际就是利用计数排序的思想。 假设所有整数都在(0,maxN)区间,利用一个数组count[maxN]来记录每个整数出现的次数。count[i]表示整数i在N个数中出现的次数。只需要扫描一遍就可以得到count数组,然后寻找第K大的元素。算法实现如下:

public static List<Integer> findTopK(int[] array, int k) {
    int max = array[0];
    for (int i = 0; i < array.length; i++) {
        if (max < array[i]) {
            max = array[i];
        }
    }
    int count[] = new int[max + 1];
    for (int i = 0; i < array.length; i++) {
        count[array[i]] += 1;
    }
    List<Integer> topKList = new ArrayList<>();
    for (int sumCount = 0, j = count.length - 1; j >= 0; j--) {
        int c = count[j];
        sumCount += c;
        if (c > 0) {
            for (int i = 0; i < c; i++) {
                topKList.add(j);
            }
        }
        if (sumCount >= k) {
            break;
        }

    }
    return topKList;
}

这是一个典型的以空间换取时间的做法。当数组中取值范围比较大时,是及其浪费空间的。如[3,1...9999],为了求出最大的K个元素,需要额外申请一个长度为10000的数组。

极端情况下,如果 N 个整数各不相同,我们甚至只需要一个 bit 来存储这个整数是否存在,这样可节省很大的内存空间。

本文部分内容参考书籍《编程之美》。

© 著作权归作者所有

AbeJeffrey
粉丝 49
博文 43
码字总数 116095
作品 0
杭州
高级程序员
私信 提问
约瑟夫问题(Josephus problem)的klog(n)解法

约瑟夫问题是一个经典的算法问题,其解决过程涉可能用到的数据结构有数组、链表,涉及的算法包括模拟、递归、递推、动态规划等等,因此非常适合做一道面试题。 问题描述: 首先n个候选人围成...

尹宁
2018/06/14
0
0
最大公约数问题

解法一 早在公元前300年,欧几里德就在《几何原本》中给出了高效的辗转相除法。欧几里得辗转相除法是现在算法的鼻祖。 算法思路(伪代码) function gcd (a, b) 算法证明 1. 两个数a、b,用a...

技术mix呢
2017/11/09
0
0
The Tower of Hanoi(汉诺塔)问题深入研究

汉诺塔问题是一个经典的“重复问题“(recurrent problem),解法也中所周知,最少移动步骤是2^n - 1。 然而,我发现,对这个问题进行进一步的研究也是挺有意思的。 本篇博客目前阐述三个Han...

ChenQi
2012/05/05
1.3K
0
LeetCode算法题-Contains Duplicate II(Java实现)

这是悦乐书的第193次更新,第197篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第53题(顺位题号是219)。给定整数数组和整数k,找出数组中是否存在两个不同的索引i和j,使得...

小川94
2018/12/06
0
0
LeetCode算法题-Pascal's Triangle II(Java实现)

这是悦乐书的第171次更新,第173篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第30题(顺位题号是119)。给定非负索引k,其中k≤33,返回Pascal三角形的第k个索引行。行索引...

小川94
2018/11/14
0
0

没有更多内容

加载失败,请刷新页面

加载更多

IDEA 拉取、上传、更新 项目到 Gitee+GitHub_超详细超简单版

注:本人使用的idea是最新版(2019.1.2),要是其他的版本的不要惊慌〜,基本上都一样,没有什么太大的差别的 首先我要说一下,拉取项目分两个,一个,你就没有项目,拉取仓库的整个项目,而...

杨木发
今天
54
0
pyqt5环境搭建(Ubuntu19.10+pycharm+python3)

1.安装pyqt5 sudo apt-get install python3-pyqt5 sudo apt-get install qttools5-dev-tools sudo apt-get install qt5-default 2.安装pycharm 下载pycharm社区版安装包并解压 在桌面新建pyc......

小芯片
今天
54
0
Vue造轮子-tab组件(中)

1. 如果给一个标签一个class,标签本身又有class,vue是默认会合并的。只有两个属性是这样一个是class,一个是style。这样就比较好改样式。 <g-tabs-head class="red"></g-tabs> 2. 组件的...

ories
昨天
59
0
Windows 版本 Anaconda 配置加速源安装软件

C:\Users\lenovo\.condarc 首先安装Anaconda最新版本。 其次添加安装目录到环境变量。文本为 C:\ProgramData\Anaconda3\Library\bin 运行 conda 命令在 Windows 用户下生成文件 .conda...

白豆腐徐长卿
昨天
232
0
如何从Bash函数返回字符串值

我想从Bash函数返回一个字符串。 我将用Java编写示例以显示我想做的事情: public String getSomeString() { return "tadaa";}String variable = getSomeString(); 下面的示例在bash中...

javail
昨天
71
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部