首页 > 试题广场 >

寻找第K大

[编程题]寻找第K大
  • 热度指数:350594 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解

有一个整数数组,请你根据快速排序的思路,找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ,请返回第 k 大的数(包括重复的元素,不用去重),保证答案存在。
要求:时间复杂度 ,空间复杂度
数据范围:,数组中每个元素满足
示例1

输入

[1,3,5,2,2],5,3

输出

2
示例2

输入

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

输出

9

说明

去重后的第3大是8,但本题要求包含重复的元素,不用去重,所以输出9        
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        def qsort(a,i,j,target):
            m = i
            n = j
            t = a[i]
            while i<j:
                while i < j and a[j]>=t:
                    j -= 1
                a[i] = a[j]
                while i < j and a[i]<=t:
                    i += 1
                a[j] = a[i]
            a[i] = t
            if i == target :
                return t
            elif i> target:
                return qsort(a, m, i-1,target)
            else:
                return qsort(a, i+1, n,target)
        return qsort(a, 0, len(a)-1,n-K)
发表于 2021-09-11 15:36:03 回复(0)
第一种解题思路: 只需这两行代码就行, 不满足题意
        sort(a.begin(), a.end());
        return a.at(n -K);
第二种解题思路:
class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        // write code here
        if (K > n)
        {
            return -1;
        }
        quick_sort(a, 0, n-1);
        
        return a[n-K];
        
    }
    
    void quick_sort(vector<int>& a, int iLow, int iUpper)
    {
        if (iLow >= iUpper)
        {
            return;
        }
        
        int iIndex = iLow;
        int jIndex = iUpper;
        int iBaseValue = a.at(iIndex);
        
        while (iIndex < jIndex)
        {
            while(iIndex < jIndex && a.at(jIndex) >= iBaseValue)
            {
                jIndex--;
            }
            
            while (iIndex <jIndex && a.at(iIndex) <= iBaseValue)
            {
                iIndex++;
            }
            
            if (iIndex < jIndex)
            {
                std::swap(a[iIndex], a[jIndex]);
            }
        }
        a[iLow] = a[iIndex];
        a[iIndex] = iBaseValue;
        
        quick_sort(a, iIndex+1, iUpper);
        quick_sort(a, iLow, iIndex-1);
        
    }
};


编辑于 2021-09-09 10:59:59 回复(1)
class Solution {
public:
    vector<int> partition(vector<int> &a,int left,int right)
    {
        int less=left-1;
        int more=right;
        while(left<more)
        {
            if(a[left]<a[right])
            {
                swap(a[++less],a[left++]);
            }
            else if(a[left]>a[right])
            {
                swap(a[--more],a[left]);
            }
            else 
            {
                left++;
            }
        }
        swap(a[right],a[more]);
        return {less+1,more};
    }
    void quicksort(vector<int> &a,int left,int right)
    {
        if(left>=right) return;
        int index=left+rand()%(right-left+1);
        swap(a[index],a[right]);
        vector<int> recv=partition(a,left,right);
        quicksort(a,left,recv[0]-1);
        quicksort(a,recv[1]+1,right);
    }
    int findKth(vector<int> a, int n, int K) {
        // write code here
        quicksort(a,0,n-1);//注意传入的是n-1不是n
        return a[n-K];
    }
};
手写快排
发表于 2021-09-06 10:24:42 回复(2)
原始快排
# -*- coding:utf-8 -*-

class Solution:
    def quick_sort(self,a,left,right,k):
        if left < right:
            mid = self.partition(a,left,right)
            if mid < k:
                self.quick_sort(a,left,mid-1,k)
            elif mid > k:
                self.quick_sort(a,mid+1,right,k)
            else:
                return a
                else:
                    return a
    def partition(self,a,left,right):
        pivot = left
        while left != right:
            while left < right and a[right] > a[pivot]:
                right -= 1
            while left < right and a[left] <= a[pivot]:
                left += 1
            if left < right:
                a[left],a[right] = a[right],a[left]
        a[pivot],a[left] = a[left],a[pivot] 
        return left
            
    def findKth(self, a, n, K):
        # write code here
        return self.quick_sort(a,0,n-1,n-K)[n-K]

根据所给K值进行剪枝优化
# -*- coding:utf-8 -*-

class Solution:
    def quick_sort(self,a,left,right,k):
        mid = self.partition(a,left,right)
        if mid == k:
            return a[mid]
        elif mid > k:
            return self.quick_sort(a,left,mid-1,k)
        elif mid < k:
            return self.quick_sort(a,mid+1,right,k)
    def partition(self,a,left,right):
        pivot = left
        while left != right:
            while left < right and a[right] > a[pivot]:
                right -= 1
            while left < right and a[left] <= a[pivot]:
                left += 1
            if left < right:
                a[left],a[right] = a[right],a[left]
        a[pivot],a[left] = a[left],a[pivot] 
        return left
            
    def findKth(self, a, n, K):
        # write code here
        return self.quick_sort(a,0,n-1,n-K)


发表于 2021-06-04 22:42:50 回复(0)
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if (a == null || n == 0 || K < 1 || K > n){
            return -1;
        }
        return partition(a, 0, n - 1, n - K);
    }
     private int partition(int[] a, int start, int end, int K) {
        if (start >= end) {
            return a[K];
        }
        
        int left = start, right = end;
        int pivot = a[(start + end) / 2];
        
        while (left <= right) {
            while (left <= right && a[left] < pivot) {
                left++;
            }
            while (left <= right && a[right] > pivot) {
                right--;
            }
            if (left <= right) {
                swap(a, left, right);
                left++;
                right--;
            }
        }
        
        if (K <= right) {
            return partition(a, start, right, K);
        }
        if (K >= left) {
            return partition(a, left, end, K);
        }
        return a[K];
    }    
    
    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
}

发表于 2021-05-07 16:58:19 回复(0)
Debug了半天,才发现是要返回第K大的数(从大到小排序....哭le......
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        if(a.length<n || n<1) return -1;
        return quick_sort(a,0,n-1,K);
    }
    
    private static int quick_sort(int[] a, int start, int end,int K){
        if(end>=start){
            int key =a[start], i=start, j=end, p=0;
            while(i<j){
                if(p==0){
                    if (a[j]>key) {
                        a[i]=a[j];
                        i++;
                        p=1;
                    }else{j--;}
                }else{
                    if(a[i]<key) {
                        a[j]=a[i];
                        j--;
                        p=0;
                    }else{i++;}
                }
            }
            if(i==K-1){
                return key;
            }else if(i>K-1){
                return quick_sort(a,start,i-1,K);
            }else{
                return quick_sort(a,i+1,end,K);
            }
        }
        return -1;
    }
}


发表于 2021-04-16 12:39:00 回复(0)
找到规律之后很简单,只需要进行去重,和排序,但是因为set插入顺序无法保证,所以一定要先去重然后排序,几句话搞定
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        //先去重,后排序
        Set set=new HashSet();
        for(int ch:a){
            set.add(ch);
        }
        Object[] arr=set.toArray();
        Arrays.sort(arr);
        int length=arr.length;
        int b=0;
        for(int i=arr.length-1;i>=0;i--){
            b=(int)arr[length-K];
            break;
        }
        return b;
    }
}


发表于 2021-04-02 09:41:31 回复(0)
每次进行一轮比较排序之后,确定一个base, 返回该base的下标, 判断是否和 n - K 相等,是则返回该数字,否则进行下一轮比较。

class Solution {
public:
    int quick_sort(vector<int> &data, int left, int right){
        int base = data[left];
        while (left < right)
        {
            while (left < right && data[right] >= base)
                --right;
            data[left] = data[right];
            while (left < right && data[left] <= base)
                ++left;
            data[right] = data[left];
        }
        data[left] = base;
        return left;
    }
    
    int findKth(vector<int> a, int n, int K) {
        int low = 0;
        int high = n -1;
        K = n - K;
        while (true)
        {
            int index = quick_sort(a, low, high);
            if (index == K)
                return a[index];
            if (index < K)
                low = index + 1;
            if (index > K)
                high = index - 1;
        }
        
    }
};


发表于 2021-03-21 13:29:13 回复(0)
import java.util.*;

public class Solution {
    /** 
    找出数组中第K大的数:表示要从大到小排,找到第k大的数字
    */
    public int findKth(int[] a, int n, int K) {
        int low = 0, high = n - 1;
        while(low <= high) {
            int i = low, j = high;
            //基准数
            int temp = a[low];
            while(i < j) {
                // 从右到左找到第一个 < temp 的数的下标
                while(i < j && a[j] <= temp) {
                    j--;
                }
                // 从左到右找到第一个 > temp 的数的下标
                while(i < j && a[i] >= temp){
                    i++;
                }
                if(i < j) {
                    // 交换下标为 i,j 的两个数
                    swap(a, i, j);
                }
            }
            //最后将基准为与i和j相等位置的数字交换
            swap(a, low, i);
            if(i == K - 1){
                return a[K-1];
            }else if(i < K - 1) {
                // K-1 位于高分段
                low = i + 1;
            }else {
                // K-1 位于低分段
                high = i - 1;
            }
        }
        return -1;
    }
    /**
    交换下标为i,j的两个元素
    */
    private void swap(int[] a, int i, int j) {
        int c = a[i];
        a[i] = a[j];
        a[j] = c;
    }
}

发表于 2020-11-15 00:14:22 回复(0)
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
		int low = 0;
		quickSort(a,low,n-1);
		return a[n-K]; //返回倒数第3个数(因为我是升序排序)
    }
 
	private  static void quickSort(int[] a, int low, int high) {
		// 递归出口
		if (low > high) { 
			return;
		}
		//标记
		int i = low;
		int j = high;
		int key = a[low];
 
		// 完成一趟快排
		while (i < j) {
			// 1.从右往左找到第一个小于key的数
			while (i < j && a[j] >key) {
				j--;
			}
			// 2. 从左往右找到第一个大于key的数
			//(刚开始少了等于,发现run了好久都没run出来,可能陷入了死循环)
			while (i < j && a[i] <= key) {
				i++;
			}
			// 3. 交换
			//if (i < j) {
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			//}
		}
 
		
		// 4.调整key的位置 (将key放到i的位置)
		a[low] = a[i];
		a[i] = key;
 
		// 递归过程
		// 5. 对key左边的数快排
		quickSort(a, low, i - 1);
		// 6. 对key右边的数快排
		quickSort(a, i + 1, high);

	}
}
时间复杂度:O(NlogN)
对数组进行快排
排序后按下标输出相应的数即可

我这里还有另一种方法:冒泡排序
时间复杂度是O(N*k)N代表数组长度,k代表几个数
感兴趣到小伙伴可以联系一下我,我会第一时间给你代码


 

编辑于 2020-10-21 17:08:19 回复(0)

单纯地用快排做了一哈排序,我的目的是为了学习快排。
这里的题意应该是用快排的思想,应该有条件可以提前结束。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here 
         int[] arr = Arrays.copyOf(a, a.length);
         quicksort(a, 0, a.length - 1);
         return a[n-K];
    }
    public void swap(int[] a, int i,int j){
        int temp = a[i];
        a[i]=a[j];
        a[j]=temp;
    }
    public int partition(int[] a,int start,int end){
        //设置基准值的索引
        int pivot = start;
        //记录下一个放比基准值小的值的索引
        int index = start+1;
        //遍历,找到比基准值小的,依次放在基准值后
        //注意这里要取end的值,因为我这end是最后的索引值
        //注意这里要取end的值,因为我这end是最后的索引值
        //注意这里要取end的值,因为我这end是最后的索引值
        //为什么说三遍,因为我一开始一直没注意
        for(int i=index;i<=end;i++){
            if(a[i]<a[pivot]){
                swap(a,i,index);
                index ++;
            }
        }
        //由于此时index位置的值必然大于等于基准值,所以把基准值和index-1位置的值互换,这样一来就排好序了
        swap(a,pivot,index-1);
        //返回的也是基准值的索引
        return index-1;
    }
    public int[] quicksort(int[] arr, int start,int end){
        if(start<end){
            //返回基准值的索引,在左边的都是比它小的
            int partition = partition(arr, start, end);
            //分别对两边进行排序
            quicksort(arr,start,partition-1);
            quicksort(arr,partition+1,end);
        }
        return arr;
    }
}


发表于 2020-10-10 21:52:32 回复(0)
先对数组进行QuickSort,降序(从大到小)排列,然后返回数组中index为K - 1的值:
import java.util.*;

public class Solution {
    /** Partition Algorithm */
    public static int partition(int[] a, int left, int right) {
        int j = left;
        int t = right;
        while (j < t) {
            if (a[j + 1] > a[j]) {
                //swap a[j + 1] and a[j]
                int temp = a[j + 1];
                a[j + 1] = a[j];
                a[j] = temp;
                j = j + 1;
            } else { // swap a[j + 1] and a[t]
                int temp = a[j + 1];
                a[j + 1] = a[t];
                a[t] = temp;
                t = t - 1;
            }
        }
        return j;
    }
    
    /** QuickSort Algorithm*/
    public static void QS(int[] a, int h, int k) {
        int h1 = h;
        int k1 = k;
        // invariant a[h..k] is sorted if a[h1..k1] is sorted
        while (k1 - h1 > 0) { // when a[h1..k1] has more than one element
            int j = partition(a, h1, k1);
            // a[h1..j-1] >= a[j] >= a[j+1..k1]
            if (j - h1 < k1 - j) { // if a[h1..j-1] smaller than a[j+1..k1]
                QS(a, h1, j - 1);
                h1 = j + 1;
            } else {
                QS(a, j + 1, k1);
                k1 = j - 1;
            }
        }
    }
    
    public int findKth(int[] a, int n, int K) {
        QS(a, 0, n - 1);
        return a[K - 1];
    }
}
编辑于 2020-09-12 12:02:05 回复(0)
1.设置初始查找区间 low=0;high=n-1;
2.以ai为轴值对序列a[low]-a[high]进行一次划分,得到轴值的位置s
3.以轴值位置s与k进行比较
3.1 如果k-1等于s,则将as作为结果返回
  3.2 如果s<k-1 则low=s+1;转步骤2。
  3.3如果s>k-1,则high=s-1;转步骤2。
找第K大的数使用降序比较方便,而找第K小数使用升序。
class Solution {
public:
    int findKth(vector<int>a, int n, int K) {
        // write code here
        int low=0,high=n-1;
        int s=partition(a,low,high);
        
        while(1){
        if(s==K-1)
            return a[s];
        else if(s<K-1)
        {    low=s+1;   
             s=partition(a,s+1,high);
        }
            else
            {    high=s-1;
                s=partition(a,low,s-1)
            }
        }
                
    }
    int partition(vector<int>&a,int low,int high)
    {
        int privot=a[low];
        while(low<high){
            while(low<high&&a[high]<=privot)high--;
            a[low]=a[high];
            while(low<high&&a[low]>=privot)low++;
            a[high]=a[low];
        }
        a[low]=privot;
        return low;
    }
};


发表于 2019-12-21 23:24:37 回复(0)
    int partit(vector<int> &a, int low, int high){
        int piov = a[low];
        while(high > low){
            while(high > low && a[high] <= piov) --high;
            a[low] = a[high];
            while(high > low && a[low] >= piov) ++low;
            a[high] = a[low];
        }
        a[low] = piov;
        return low;
	}
    int findKth(vector<int> a, int n, int K) {
        // write code here
        int pos = 0;
        int high = n-1, low = 0;
        while(high >= low){
            pos = partit(a, low, high);
            if(pos == K-1) break;
            else if(pos < K-1)
                low = pos+1;
            else
                high = pos-1;
        }
        return a[pos];
    }

发表于 2016-09-04 15:05:09 回复(0)
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here 
        quickSort(a,0,n-1);
        return a[n-K];//看清楚是第K大,不是第K小,我是从小到大排的数
    }
//下面是快排经典代码
    public void quickSort(int[] a,int start,int end){
        if(start<end){
            int i=partition(a,start,end);
            quickSort(a,i+1,end);
            quickSort(a,start,i-1);
        }
    }
    public int partition(int[]a,int p,int q){//以数组第一个数为基准将数组分为左右两部分,左边小于基数,右边大于基数,然后把基数放在数组中合适的位置,返回该位置
        int x=a[p];
        int i=p;
        for(int j=p+1;j<=q;j++){
            if(a[j]<x){
                swap(a,i+1,j);
                i++;
            }
        }
        swap(a,p,i);
        return i;
    }
    public void swap(int[]a ,int i,int j){
        int temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }
}

发表于 2016-06-30 15:44:56 回复(2)
# -*- coding:utf-8 -*-

class Solution:
    def findKth(self, a, n, K):
        # write code here
        for i in range(K-1):
            a.pop(a.index(max(a)))
        return max(a)

发表于 2021-07-14 16:29:34 回复(0)
import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        Arrays.sort(a);
        return a[n-K];
    }
}

发表于 2017-04-05 20:29:24 回复(3)
#这大概是作弊吧
class Solution:
    def findKth(self, a, n, K):
        # write code here
        return sorted(a)[n-K]

发表于 2020-09-28 10:34:31 回复(1)
//使用快排,按照从大到小排序
int quickSortKth(vector<int> a, int start,int end, int K)
    {
        //划分
        int left,right;
        int pivot,temp;
        left = start;
        right = end-1;
         pivot = a[left];
        while (left < right){
            while (left < right && a[right] <= pivot){
                right --;
            }
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;

            while (left < right && a[left] >= pivot){
                left ++;
            }
            temp = a[left];
            a[left] = a[right];
            a[right] = temp;
        }
        a[left] = pivot; //找到划分位置

        if(K == left+1){
            return a[left];
        }else if(K < left+1){
            return quickSortKth(a,start,left,K);
        }else if(K > left+1){
            return quickSortKth(a,left+1,end,K);
        }
        return -1;
    }

    int findKth(vector<int> a, int n, int K) {
        return quickSortKth(a,0,n,K);
    }

编辑于 2016-08-02 16:11:16 回复(0)
importjava.util.*;
 
public clas sSolution {
    public int findKth(int[] a, intn, intK) {
        quickSort(a,0, n-1);
        return a[n-K];
    }
    public static void quickSort(int source[], int low, int high){ 
        inti,j,x; 
        if(low<high){ 
            i= low; 
            j= high; 
            x= source[i]; 
            while(i<j){ 
                while(i<j &&source[j]>x){ 
                    j--; 
                } 
                if(i<j){ 
                    source[i]=source[j]; 
                    i++; 
                } 
                while(i< j&&source[i]<x){ 
                    i++; 
                } 
                if(i<j){ 
                    source[j]=source[i]; 
                    j--; 
                } 
            } 
            source[i]=x; 
            quickSort(source,low,i-1); 
            quickSort(source,i+1,high); 
        } 
    } 
}

编辑于 2016-04-01 10:22:20 回复(0)