挑战面试编程:查找数组中第k大的数

查找数组中第k大的数

问题:

查找出一给定数组中第k大的数。例如[3,2,7,1,8,9,6,5,4],第1大的数是9,第2大的数是8……

思路:

1. 直接从大到小排序,排好序后,第k大的数就是arr[k-1]。

2. 只需找到第k大的数,不必把所有的数排好序。我们借助快速排序中partition过程,一般情况下,在把所有数都排好序前,就可以找到第k大的数。我们依据的逻辑是,经过一次partition后,数组被pivot分成左右两部分:S左、S右。当S左的元素个数|S左|等于k-1时,pivot即是所找的数;当|S左|小于k-1,所找的数位于S右中;当|S左|>k-1,所找的数位于S左中。显然,后两种情况都会使搜索空间缩小。

代码:

int Partition(int *arr, int from, int to)
{
    int i, j;
    i = j = from;
    while (j <= to)
    {
        if (arr[j] >= arr[to]) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
        }
        j++;
    }
    return i - 1;
}
int quickSelect(int *s, int k, int left, int right)
{
    if (left == right) return s[left];
    int i;
    i = Partition(s, left, right);
    if (i - left + 1 == k) {
        return s[i];
    }
    else if (i - left + 1 < k) {
        return quickSelect(s, k - (i - left + 1), i + 1, right);
    }
    else return quickSelect(s, k, left, i - 1);
}
int findKthLargest(int* nums, int numsSize, int k) {
    return quickSelect(nums, k, 0, numsSize - 1);
}

至于”查找数组中第k小的数“,那自然可以举一反三,同样处理了。

代码下载:查找数组中第k大的数

所有内容的目录

时间: 01-06

挑战面试编程:查找数组中第k大的数的相关文章

[经典算法题]寻找数组中第K大的数的方法总结

[经典算法题]寻找数组中第K大的数的方法总结 责任编辑:admin 日期:2012-11-26 字体:[大 中 小] 打印复制链接我要评论 今天看算法分析是,看到一个这样的问题,就是在一堆数据中查找到第k个大的值. 名称是:设计一组N个数,确定其中第k个最大值,这是一个选择问题,当然,解决这个问题的方法很多,本人在网上搜索了一番,查找到以下的方式,决定很好,推荐给大家. 所谓"第(前)k大数问题"指的是在长度为n(n>=k)的乱序数组中S找出从大到小顺序的第(前)k个数的问题.

【LeetCode-面试算法经典-Java实现】【215-Kth Largest Element in an Array(数组中第K大的数)】

[215-Kth Largest Element in an Array(数组中第K大的数)] [LeetCode-面试算法经典-Java实现][所有题目目录索引] 代码下载[https://github.com/Wang-Jun-Chao] 原题 Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth d

找一个数组中第K大的数

快排思想,选取序列的一个key进行划分,小于key的分在左边,大于key的在右边,key的位置-low+1就是最后一个元素是key的序列中元素的数量,当元素数量大于K时,就在左半部分递归找,等于时 arr[key]就是第K 大的元素,小于K时,在右边递归找第k-num大的元素 /** * 文件名:FindK.java * 时间:2014年11月7日上午11:23:43 * 作者:修维康 */ package chapter7; /** * 类名:FindK 说明:找到一个数组中第K大的元素 */

查找无序数组中第K大的数

思路: 利用快速排序的划分思想 可以找出前k大数,然后不断划分 直到找到第K大元素 代码: #include <iostream> #include <algorithm> #include <cstdio>5 using namespace std; int findK(int left, int right, int arr[], int k) { if(left >= right) return arr[left]; int first = left, la

求数组中第k大的数(分治法)

思想:快排 因为单趟排序是使选定的king值到其应该到的位置,所以每次判断这个king的正确位置是否是第K大数的位置即可 #include <iostream> using namespace std; //快排中的单趟排序 int PartSort(int* arr,int start,int end) { int first = start; int last = end; int tmp = arr[first]; int key = first; while (first < l

【滴滴笔试】1.连续数组的最大和 2.找出数组中第K大的数

1 import java.util.Arrays; 2 import java.util.Scanner; 3 public class Main { 4 public static void main(String args[]){ 5 Scanner scanner = new Scanner(System.in); 6 while (scanner.hasNext()){ 7 String str = scanner.nextLine(); 8 String[] arrStr = str

数组中第K大的元素

数组中第K大的元素总结 解法1: 我们可以对这个乱序数组按照从大到小先行排序,然后取出前k大,总的时间复杂度为O(n*logn + k). 解法2: 如果k很小,比如第五个最大的数,而整个数组的长度非常的大,那么,还有一种方法就是,我做k遍找最大的数,每做一遍,就把最大的放在数组的最后面(遍历一次找出最大的数例如冒泡,选择排序都可以.),然后减少数组扫描的范围,就可以把第k大的数找出来,这样做的复杂度就是O(K*N),在K很小的情况下,还是不错的. 解法3: 利用快速排序的思想,从数组S中随机找

算法导论:快速找出无序数组中第k小的数

题目描述: 给定一个无序整数数组,返回这个数组中第k小的数. 解析: 最平常的思路是将数组排序,最快的排序是快排,然后返回已排序数组的第k个数,算法时间复杂度为O(nlogn),空间复杂度为O(1).使用快排的思想,但是每次只对patition之后的数组的一半递归,这样可以将时间复杂度将为O(n). 在<算法导论>有详细叙述 这里主要用C++实现,实现思路就是先选取当前数组的第一个数作为"主轴",将后面所有数字分成两部分,前面一部分小于"主轴",后面一部

[LeetCode] Kth Largest Element in an Array 数组中第k大的数字

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element. For example, Given [3,2,1,5,6,4] and k = 2, return 5. Note: You may assume k is always valid, 1 ≤ k ≤ array'