寻找第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

tornado123

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)

Java

JaxonSuzy

单纯地用快排做了一哈排序，我的目的是为了学习快排。

这里的题意应该是用快排的思想，应该有条件可以提前结束。

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)

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)

高高的围墙

    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)

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)

Python 3

牛客152785677号

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

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)

我就是爱音乐


	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)

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)

阿Q想offer

简洁Java，了解一下

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];
    }
}

发表于 2020-08-06 23:50:45 回复(4)

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)

寻找第K大

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题