文档章节

寻找最大的K个数: 终极解决方案

zongjh
 zongjh
发布于 2017/05/19 12:30
字数 1555
阅读 27
收藏 0

(终于等到你)

 

写在前面的一句话:那些年,虐过你的面试题是:_______。

 

 

 

今天继续和大家聊寻找最大的K个数。

 

先来熟悉一下问题:

有很多个无序的数(我们这里假设为正整数),而且各不相等,怎么选出最大的K个数。

 

例如:2,5,7,1,3,9,3,6,7,8,5

最大的5个数为:7,9,6,7,8

 

之前我们给出了四种解法:

快速排序和选择排序,文章详情:寻找最大的K个数:快排和选择(一)

快排优化和二分搜索,文章详情:寻找最大的K个数:快排优化和二分搜索(二)

 

今天我们继续。开始前,先聊一会。

 

最终的那个方案,时间复杂度是线性的,也就是说,效率是六个解法中最高的。但是,它有自己的限制。

首先,所有的N个数都是正整数。

其次,它们的取值范围都不太大。

 

这里想说一个什么问题呢?有所长,必有所短!

 

老天给你打开了一扇窗,一定会给你关闭一扇门。

 

老天给你打开了一扇门,一定会给你打开一扇窗。

 

如果你好,那么你一定有某些限制;如果你慢,那么你一定有其它优点。请相信,只要存在,就是合理。

 

拿世界上最好的编程语言php来说(没有之一),随修改,随运行,那叫一个6666。但是缺点也是很多,至于什么,请自行百度。

 

道理很简单,如果一个语言,又快,又好,那么其它编程语言就可以去死了。现在其它语言都活的好好的。

 

所以,在什么情况下选择什么语言,是非常明智的,也是聪明的。不要一味地抱残守缺!

 

其实我很不理解一件事,就是面试问那么多高深的技术,进去之后还是去写业务代码。门槛如此之高,进去之初很容易摔跤。

 

先来说说最小堆的事。

 

假如,我们有一个大小为K的数组,数组是一个最小堆(数组第一个数为整个数组最小的值)。请自行百度什么是最小堆。

 

我们从数组S中取一个值,这个值和最小堆的第一个数first对比,有两种结果:

1,Si <= first  那么我们可以不做任何处理,因为我们找的是最大的K个数

2,Si > first 这时候,我们需要将Si的值赋值给最小堆的首元素。这时候我们可能会破坏最小堆的结构,所以需要重建最小堆。重建后,第一个元素同样是最小的。就这样一次比较下去。

 

不知道看没看明白,我们只需要一次将数组S中的元素与最小堆的首元素相比即可。

代码如下:

package com.xylx.utils.selectK;

import com.xylx.utils.GsonUtils;

/**
 * Created by  on 17-5-10.
 */
public class MinHeap {
    public static void main(String[] args) {
        int[] arr = {2,6,3,9,4,8};
        buildMinHeap(arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));

        change(5, arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));

        change(6, arr);
        System.out.println(GsonUtils.getJsonFromObject(arr));
    }

    /**
     * 都建构建最小堆
     * @param arr
     */
    public static void buildMinHeap(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            handleMinHeap(arr, arr.length, i); //从前向后构建最小堆
        }
    }

    /**
     * 检查value是否比arr[0]大,如果大于,则对堆进行重构
     * @param value
     * @param arr
     */
    public static void change(int value, int[] arr) {
        if (value > arr[0]) {
            arr[0] = value;
            handleMinHeap(arr, arr.length, 0);
        }
    }

    /**
     * 最小堆排序
     * @param arr
     */
    public static void minHeapSort(int[] arr) {
        for (int i=arr.length-1; i>0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            handleMinHeap(arr, i, 0);
        }
    }

    /**
     * 节点转换
     * @param arr
     * @param heapSize
     * @param current
     */
    public static void handleMinHeap(int[] arr, int heapSize, int current) {
        int leftChildIndex = getLeftChiledIndex(current);
        int rightChildIndex = getRightChildIndex(current);
        int minIndex = current; //找到三个节点中最小的那个
        if (leftChildIndex<heapSize && arr[current] > arr[leftChildIndex]) {
            minIndex = leftChildIndex;
        }
        if (rightChildIndex<heapSize && arr[minIndex] > arr[rightChildIndex]) {
            minIndex = rightChildIndex;
        }
        if (minIndex != current) {
            int tmp = arr[current]; //将最小的值转移到父节点位置,这样可能会破坏原先子节点的结果,所以需要递归
            arr[current] = arr[minIndex];
            arr[minIndex] = tmp;
            handleMinHeap(arr, heapSize, minIndex);
        }
    }

    /**
     * 获取左孩子节点位置
     * @param current
     * @return
     */
    public static int getLeftChiledIndex(int current) {
        return (current<<1) + 1;
    }

    /**
     * 获取右孩子节点位置
     * @param current
     * @return
     */
    public static int getRightChildIndex(int current) {
        return (current<<1) + 2;
    }

    /**
     * 获取父节点位置
     * @param current
     * @return
     */
    public static int getParentIndex(int current) {
        return (current-1)>>1;
    }
}

 

说完了上面那个,让我们看看最终的大boss。

 

下面这个是面试中大部分面试官想要的结果。它的工作流程是:

得到数组中最大的值MAX,这样数组中所有的数都在[0, MAX]之间。申请一个数组countArr,大小为MAX+1。countArr每条记录是这个下标所代表的数组在数组中出现的次数。这样,我们只需要从前向后找到前K个最大的数即可。

 

代码如下:

package com.xylx.utils.selectK;

/**
 * Created by zongjh on 17-5-8.
 */
public class FinalSelectK {
    public static void main(String[] args) {
        int[] arr = Constans.getLengthArr(100);
        Constans.printArr(arr);
        selectK(arr);
    }

    public static void selectK(int[] arr) {
        int max = getMax(arr);
        System.out.println("max="+max);
        int[] countArr = new int[max+1];
        initArr(countArr);
        for (int i=0; i<arr.length; i++) {
            int index = arr[i];
            countArr[index] = countArr[index] + 1;
        }
        int num = getK(countArr, max);
        System.out.println("num="+num);
        printK(arr, num);
    }

    private static void printK(int[] arr, int min) {
        int index = 0;
        System.out.println("最大的K个数:");
        for (int i=0; i<arr.length; i++) {
            if (arr[i] > min) {
                System.out.print(arr[i]+"    ");
                index++;
            }
        }
        for (int i=0; i<(Constans.K-index); i++) {
            System.out.print(min+"    ");
        }
    }

    /**
     * 寻找第K大的数
     * @param countArr
     * @param max
     * @return
     */
    public static int getK(int[] countArr, int max) {
        int num = 0;
        int sumCount = 0;
        for (int i=max-1; i>0; i--) {
            sumCount += countArr[i];
            if (sumCount >= Constans.K) {
                num = i;
                break;
            }
        }
        return num;
    }

    public static void initArr(int[] arr) {
        for (int i=0; i<arr.length; i++) {
            arr[i] = 0;
        }
    }

    /**
     * 得到数组最大值
     * @param arr
     * @return
     */
    public static int getMax(int[] arr) {
        if (arr == null || arr.length < 1) {
            return Integer.MIN_VALUE;
        }
        int max = Integer.MIN_VALUE;
        for (int i=0; i<arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        return max;
    }
}

 

这里的辅助类,请参考之前的文章,看开头。

 

终于写完了,这个寻找最大的K个数。

 

最后一句话:说不定哪天你就用到这个面试题了!

 

其他技术文章:

DNS域名解析

CDN知道为什么是你?

靠谱的TCP:三次握手和四次挥手

喜欢聊技术或者聊观点,可以加入公号:【花生读书汇】

一起:励志,成长,学习,分享。

【花生读书汇】

© 著作权归作者所有

共有 人打赏支持
zongjh
粉丝 1
博文 39
码字总数 12405
作品 0
东城
程序员
私信 提问
寻找最大的K个数,Top K问题的堆实现

前两天面试3面学长问我的这个问题(想说TEG的3个面试学长都是好和蔼,希望能完成最后一面,各方面原因造成我无比想去鹅场的心已经按捺不住了),这个问题还是建立最小堆比较好一些。 先拿100...

天天顺利
05/18
0
0
Python3机器学习实践:集成学习之LightGBM

本文为官方文档翻译,点击查看英文原版。 LightGBM(Light Gradient Boosting Machine)是微软的开源分布式高性能Gradient Boosting框架,使用基于决策树的学习算法。下面介绍下此框架的优化。...

AiFan
12/12
0
0
IPFS协议层深入分析6—Kademlia安全改进

本节我们介绍S/Kademlia路由协议,解决上一节提到的各种安全问题。 首先是更加安全的节点编号生成规则。如果我们能够限制参与者随意选择节点ID的情况,那么我们就可以规避日食攻击,因为一旦...

西二旗李老师
07/19
0
0
《R语言实战》第四部分第十六章-聚类分析学习笔记

5月初带病出了一趟差,舟车劳顿,回来以后咳嗽不止,修整了一段时间,这才缓过劲来,这方面的学习也因此耽误了几天,接下去要抓紧补回来了。 聚类分析是一种无约束的数据分析方法,其目的在于...

Datacruiser
2017/06/07
0
0
334_Increasing_Triplet_Subsequence

Increasing Triplet Subsequence Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array. Formally the function should: Return true......

大培哥
2016/04/15
233
0

没有更多内容

加载失败,请刷新页面

加载更多

我的Linux系统九阴真经

我的Linux系统九阴真经 在今天,互联网的迅猛发展,科技技术也日新月异,各种编程技术也如雨后春笋一样,冒出尖来了。各种创业公司也百花齐放百家争鸣,特别是针对服务行业,新型互联网服务行...

linuxCool
48分钟前
12
0
Python程序员需要知道的30个技巧

1 直接交换两个数字位置 1x, y = 10, 202print(x, y)3x, y = y, x4print(x, y)5#1 (10, 20)6#2 (20, 10) 2 比较运算符的链接 1n = 102result = 1 < n < 203print(result)4# True5result = 1 ......

糖宝lsh
48分钟前
9
0
[LintCode] Linked List Cycle(带环链表)

描述 给定一个链表,判断它是否有环。 样例 给出 -21->10->4->5, tail connects to node index 1,返回 true。 这里解释下,题目的意思,在英文原题中,tail connects to node index 1 表示的...

honeymose
59分钟前
10
0
Android :报错Your project path contains non-ASCII characters.

报错内容如下 Your project path contains non-ASCII characters. This will most likely cause the build to fail on Windows. Please move your project to a different directory. See ht......

lanyu96
今天
7
0
Nginx平滑添加模块

Nginx已经编译安装并运行了一段时间, 然后某一天, 发现需要用到某个模块但当初没有编译, 这个时候怎么办呢? 卸载重新安装肯定可以的, 如果Nginx版本没有变更的话, 则有一个相对平滑的方法来添...

老菜鸟0217
今天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部