美文网首页
无序数组找第K大的数

无序数组找第K大的数

作者: 西5d | 来源:发表于2018-12-29 16:26 被阅读7次

1、使用HashMap或者Queue保存

如果是少量的数据,比如K=2,3等可以使用,如2,保存到HashMap找最大,合计为2N次比较。

2、典型解法:快速排序分组。

在数组中找到第k大的元素
取基准元素,将元素分为两个集合,一个集合元素比基准小,另一个比基准大 ,三种情况。
1.比基准大的元素数目标志位m正好为k-1,基准就是目的元素。
2.比基准大的元素标志位m小于k, 那么就在比基准小的集合里面找第(k-m)大的元素
3.若是比基准大的元素为m大于k,那就继续在该集合里面找第k大的元素。
如下是代码:

 static void findKMax(int[] arr, int left, int right, int k) {
        int temp = partition(arr, left, right);
        if (temp == k - 1) {
            System.out.println(arr[temp]);
        } else if (temp > k - 1) {
            findKMax(arr, left, temp - 1, k);
        } else {
            findKMax(arr, temp + 1, right, k - temp);
        }
    }

 static int partition(int[] arr, int left, int right) {
        int temp = arr[left];
        while (left < right) {
            while (temp >= arr[right] && left < right)
                --right;
            arr[left] = arr[right];
            while (temp <= arr[left] && left < right)
                ++left;
            arr[right] = arr[left];
        }

        arr[right] = temp;
        return right;
    }
    public static void main(String[] args) {
        int[] arr = new int[] { 12, 23, 2, 3, 2, 432, 43, 534, 5, 345, 3453, 53, 43 };
        findKMax(arr,0,arr.length - 1,2);
    }

相关文章

  • 无序数组找第K大的数

    1、使用HashMap或者Queue保存 如果是少量的数据,比如K=2,3等可以使用,如2,保存到HashMap找...

  • 数组小题目

    如何找到无序数组中第K大的数?利用快速排序的思想,每次找到某节点的最终位置来缩小检索数组的大小

  • 2018-09-27 215. Kth Largest Elem

    题意:给你一个无序数组,返回该数组第K大的数(重复的两个数算两个)。解题思路:使用优先队列priority_que...

  • 算法分析 [最大/小值] 2019-02-28

    1. 数组,查找第k大值 215. 数组中的第K个最大元素(元素不重复无序) Kth Largest Elemen...

  • 数组中第K大的数

    一、相关概念 二、题目 题目 一个未排序的数组中找第k大的数 思路 快排 代码 参考文献 数组中的第K个最大元素

  • LeetCode 215. Kth Largest Elemen

    @(LeetCode) 问题描述 找出数组中第 k 个最大的数。注意是数组排序后第 k 大的数,而不是去重后的第 ...

  • bfprt算法

    前言 在一个数组中求其第k大或者第k小的数的问题(其实就是找按降序或升序排好序的数组的下标为k-1的元素),简称T...

  • Leetcode.215.Kth Largest Element

    题目 给定一个数组, 输出第k大的数. 思路 进行从大到小排序, 第k-1即为第k大的数. 总结 掌握快速排序.

  • 数字和SUM

    两数和 题意是给出一个数组,输出和为k的两个数。数组为无序的 三数和 从给定的数组中找三个数,让它们的和为某个值。...

  • 2020-04-06

    针对215题,随机选择,找无序数组中第K 大的元素。 这里注意,非递归的实现,以及分区函数(独立写法)的左右双指针...

网友评论

      本文标题:无序数组找第K大的数

      本文链接:https://www.haomeiwen.com/subject/tukplqtx.html