寻找第K大__牛客网

Python 3

昊天明月

# -*- 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)

C++

卟离forever

第一种解题思路：只需这两行代码就行，不满足题意
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)

C++

the幻云

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)

Python

wengJJ

原始快排

# -*- 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)

Setla

找到规律之后很简单，只需要进行去重，和排序，但是因为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)

Java

牛客590837641号

先对数组进行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)

shimianmaifu

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)

Java

牛客699558号

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)

从前从前有个人爱你很久

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)

Python

李寻七

#这大概是作弊吧
class Solution:
def findKth(self, a, n, K):
# write code here
return sorted(a)[n-K]

发表于 2020-09-28 10:34:31 回复(1)

Echo001

//使用快排，按照从大到小排序
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)

selfboot

class Solution {
public:
    int partition(vector<int> &nums, int begin, int end) {
        int pivot = nums[begin];
        int pivot_index = begin;
        for(int i=begin+1; i!=end;i++){
            if(nums[i] >= pivot){
                pivot_index+=1;
                if(pivot_index != i){
                    swap(nums[i], nums[pivot_index]);
                }
            }
        }
        swap(nums[begin], nums[pivot_index]);
        return pivot_index;
    }

    int findKth(vector<int> &nums, int n, int k) {
        return find_k(nums, 0, nums.size(), k);
    }

    int find_k(vector<int> &nums, int begin, int end, int k){
        if( k<=0 || begin>end-1){
            return -1;
        }
        int position = partition(nums, begin, end);
        int left_length = position-begin;
        if(left_length== k-1){
            return nums[position];
        }
        else if(left_length > k-1){
            return find_k(nums, begin, position, k);
        }
        else{
            return find_k(nums, position+1, end, k-left_length-1);
        }
    }
};

发表于 2016-03-31 10:29:12 回复(0)

ljcmeng

这题应该是用快排的思想：例如找49个元素里面第24大的元素，那么按如下步骤：

1.进行一次快排（将大的元素放在前半段，小的元素放在后半段）,假设得到的中轴为p

2.判断 p - low + 1 == k ，如果成立，直接输出a[p]，（因为前半段有k - 1个大于a[p]的元素，故a[p]为第K大的元素）

3.如果 p - low + 1 > k，则第k大的元素在前半段，此时更新high = p - 1，继续进行步骤1

4.如果p - low + 1 < k，则第k大的元素在后半段，此时更新low = p + 1, 且 k = k - (p - low + 1)，继续步骤1.

由于常规快排要得到整体有序的数组，而此方法每次可以去掉“一半”的元素，故实际的复杂度不是o(nlgn), 而是o(n)。

附上代码：

public class Solution {

public int findKth(int[] a, int n, int K) {

return findKth(a, 0, n-1, K);

}

public int findKth(int[] a, int low, int high, int k) {

int part = partation(a, low, high);

if(k == part - low + 1) return a[part];

else if(k > part - low + 1) return findKth(a, part + 1, high, k - part + low -1);

else return findKth(a, low, part -1, k);

}

public int partation(int[] a, int low, int high) {

int key = a[low];

while(low < high) {

while(low < high && a[high] <= key) high--;

a[low] = a[high];

while(low < high && a[low] >= key) low++;

a[high] = a[low];

}

a[low] = key;

return low;

}

发表于 2016-04-02 16:53:50 回复(15)

猫的树

主体思路就是利用快速排序每次能将比某个哨兵小的数放在左侧，大的数放在右侧，代码如下：

class Solution {
public:
    int findKth(vector<int> a, int n, int K) {
        return quickfind(a, 0, n-1, K);
    }
     
    int quickfind(vector<int>& a, int left, int right, int k) {
        int i = left;
        int j = right;
        int mark = a[left];
         
        while (i < j) {
            while (i < j && a[j] >= mark)
                --j;
            if (i < j)
                a[i++] = a[j];
             
            while (i < j && a[i] <= mark)
                ++i;
            if (i < j)
                a[j--] = a[i];
        }
        a[i] = mark;
         
        //哨兵右侧比他大的数字个数
        int big_num = right - i;
        
        //如果哨兵刚好是第K大的数
        if (k - big_num - 1 == 0)
            return mark;
        else if (k - big_num - 1 > 0) {
            //如果右侧数字个数不够K个，则从左侧找第k-big_num-1大的数
            return quickfind(a, left, i - 1, k - big_num - 1);
        } else {
            //如果右侧数字个数比K多，则在右侧找第K大的数
            return quickfind(a, i + 1, right, k);
        }
    }
};

编辑于 2016-07-03 19:23:15 回复(6)

牛客893890280号

这题的测试用例有问题吧，[1332802,1177178,1514891,871248,753214,123866,1615405,328656,1540395,968891,1884022,252932,1034406,1455178,821713,486232,860175,1896237,852300,566715,1285209,1845742,883142,259266,520911,1844960,218188,1528217,332380,261485,1111670,16920,1249664,1199799,1959818,1546744,1904944,51047,1176397,190970,48715,349690,673887,1648782,1010556,1165786,937247,986578,798663],49,24

用例输出是986578，我本地跑的结果是937247，提交运行的结果居然是name Solution is not defined，我都没写过Solution这个函数，怎么跑的嘛

仔细数了下，986578是第26个数

发表于 2020-11-19 11:46:11 回复(25)

Mono_Chrome

Java解法

核心思想：构建大小为K的小根堆。
时间复杂度：O(n * logK)

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        // 构建小根堆
        for (int i = 0; i < K; i++) {
            heapInsert(a, i);
        }
        for (int i = K; i < n; i++) {
            if (a[i] >= a[0]) {
                swap(a, 0, i);
                heapify(a, 0, K);
            }
        }
        return a[0];
    }

    public void heapInsert(int[] arr, int index) {
        while (arr[index] < arr[(index - 1) / 2]) {
            swap(arr, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    public void heapify(int[] arr, int index, int size) {
        int left = 2 * index + 1;
        while (left < size) {
            int smallest = left + 1 < size && arr[left + 1] < arr[left] ? 
                left + 1 : left;
            if (arr[smallest] < arr[index]) {
                swap(arr, index, smallest);
            } else {
                break;
            }
            index = smallest;
            left = 2 * index + 1;
        }
    }

    public void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

发表于 2021-06-12 16:56:57 回复(0)

JavaScript

splwany

function findKth( a ,  n ,  K ) {
    return quickfind(a, 0, n - 1, K);
}
function quickfind(a, left, right, k) {
    let i = left, j = right, pivot = a[left];
    while (i < j) {
        while (i < j && a[j] >= pivot) j--;
        if (i < j) a[i++] = a[j];
        while (i < j && a[i] <= pivot) i++;
        if (i < j) a[j--] = a[i];
    }
    a[i] = pivot;
    
    const deltaK = k - right + i - 1;
    if (deltaK === 0) return pivot;
    else if (deltaK > 0) return quickfind(a, left, i - 1, deltaK);
    else return quickfind(a, i + 1, right, k);
}

发表于 2021-04-03 10:57:54 回复(0)

LittleBaby

思想就是快速排序的划分，每次划分都会最终确定一个元素的位置，如果这个位置正好是第K大数，那么就找到了；如果小于第K大数，则在右边继续寻找；否则，在左边继续寻找。下面给出一种非递归方法。

class Solution {

public:

int findKth(vector<int> a, int n, int K) {

int low = 0, high = n - 1;

int ret = 0;

while(low<=high)//此while每循环一次，都会最终确定一个元素的位置

{//

int tmp = a[low];

int l = low, h = high;

while(low<high)

{

while(high>low && a[high]>tmp) high--;//从右往左找

a[low] = a[high];

while(low<high && a[low]<tmp) low++;//从左往右找

a[high] = a[low];

}

a[low] = tmp;//最终确定tmp的位置

if(low+1==n-K+1)

{ //找到

ret = a[low];

break;//立即退出

}

else if(low+1<n-K+1)

{//向右边

low = high + 1;

high = h;

}

else

{//向左边

high = low - 1;

low = l;

}

return ret;

}

};

编辑于 2016-09-05 00:22:14 回复(0)

Java

牛客891988436号

import java.util.*;

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

发表于 2021-09-01 10:33:31 回复(0)

寻找第K大

输入

输出

输入

输出

说明

Java解法

问题信息

热门推荐

通过挑战的用户

相关试题