【28】一个无序的序列查找第K大的数

简介: 题目:给定一个无序序列和一个数k,求这个无序序列中第K大的数分析:方案一:最朴素的方法利用快速排序然后找到第k个数,时间复杂度O(nlogn)方案二:根据快速排序中的partition方法,每次可以把一个序列分成两个部分,左边全部小于等于基准,右边的全部大于等于基准。


题目:给定一个无序序列和一个数k,求这个无序序列中第K大的数


分析:

方案一:最朴素的方法利用快速排序然后找到第k个数,时间复杂度O(nlogn)

方案二:根据快速排序中的partition方法,每次可以把一个序列分成两个部分,左边全部小于等于基准,右边的全部大于等于基准。如果partition方法中基准的位置刚好是第k个则可以直接得多这个数,如果大于k说明在左边,如果小于k说明在右边。

              利用这个方法每次可以将序列不断的划分直至找到这第k个数, 因为partition函数的时间复杂度最大为O(n),而我们每次都可以把序列分成一半,因此总的时间复杂度还是O(n)。

              时间复杂度的证明:

              1. 假设总的元素个数有n个,则

                  第一次枚举n个数

                  第二次枚举n/2

                  第三次枚举n/4

                  ...................1

              2. 则总的时间为n+n/2+n/4+....+1 <= 2n,因此时间复杂度为O(n)


举例:

例如无序序列为0 9 -1 6 7 3 5,k为3则第k大的数为6。


实例代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

//Partition方法
int Partition(int *arrNum, int l, int r){
	//不合法数据 
	if(arrNum == NULL || l > r){
        return -1;
    }
    int mid = (l+r)>>1;
	swap(arrNum[mid], arrNum[r]);
	int leftSeqIndex = l;
	//枚举区间 
	for(int i = l; i < r; i++){
	    if(arrNum[i] < arrNum[r]){
           if(i > leftSeqIndex){
		   		swap(arrNum[i], arrNum[leftSeqIndex]);
   		   }
   		   ++leftSeqIndex;
		}
    } 
    //基准交换回来
	swap(arrNum[leftSeqIndex], arrNum[r]);
	return leftSeqIndex; 
}

//求第k大的数
int GetNumber(int *arrNum, int n, int k){
	//输出-1表示不合法 
	if(arrNum == NULL || n <= 0 || k <= 0 || k > n){
        return -1;
    }
    //第k大的数等价于找第n-k+1小的数
	k = n-k+1;
	int l = 0;
	int r = n-1;
	while(l <= r){
	    int index = Partition(arrNum, l, r);
		if(index+1 == k){ //找到 
            return arrNum[index];
        }
        else if(index+1 < k){ //在右边序列找
		    l = index+1; 
	    }
	    else{ //在左边序列找 
	        r = index-1;
	    }
	}
} 

int main(){
   int arrNum[] = {0,9,-1,6,7,3,5};
   int value = GetNumber(arrNum, 7, 3);
   if(value == -1){
       cout<<"no found number";
   }
   else{
       cout<<value<<endl; 
   }

   getchar();
   return 0;
}

/*
输出
6
*/ 



目录
相关文章
|
17天前
查找数组中最小的元素
【10月更文挑战第30天】查找数组中最小的元素。
31 5
|
3月前
|
算法
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
【算法】二分查找——在排序数组中查找元素的第一个和最后一个位置
|
3月前
|
算法 索引
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
这篇文章介绍了LeetCode第34题"在排序数组中查找元素的第一个和最后一个位置"的解题方法,通过使用双指针法从数组两端向中间同时查找目标值,有效地找到了目标值的首次和最后一次出现的索引位置。
LeetCode第34题在排序数组中查找元素的第一个和最后一个位置
|
6月前
|
算法 测试技术 C#
C++二分查找或并集查找:交换得到字典序最小的数组
C++二分查找或并集查找:交换得到字典序最小的数组
|
6月前
|
存储 算法 Java
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
数据结构和算法面试题:给定一个整数数组 nums,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
88 0
|
算法
【算法专题突破】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(17)
【算法专题突破】二分查找 - 在排序数组中查找元素的第一个和最后一个位置(17)
64 0
|
C语言
C语言:输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。
描述 输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。 输入描述: 输入包含三行, 第一行包含两个正整数n, m,用空格分隔。n表示第二行第一个升序序列中数字的个数,m表示第三行第二个升序序列中数字的个数。 第二行包含n个整数,用空格分隔。 第三行包含m个整数,用空格分隔。
278 0
C语言:输入两个升序排列的序列,将两个序列合并为一个有序序列并输出。
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
LeetCode-34 在排序数组中查找元素的第一个和最后一个位置
|
人工智能
有序序列中插入一个整数
有序序列中插入一个整数
81 0
|
算法 C语言 C++
【二分查找】34. 在排序数组中查找元素的第一个和最后一个位置
二分查找是一种高效的查找算法,其时间复杂度为 O(log n)。在许多情况下,我们需要在一个有序数组中找到某个目标值的搜索范围。本文将介绍一种基于二分查找的搜索范围查找算法,该算法能够快速找到目标值在数组中的起始和结束位置。
73 0
下一篇
无影云桌面