LeetCode Brush Title _215: The K Largest Element in the Array [C++]

Topic Description

Find the kth largest element in an unordered array. Note that what you need to look for is the kth largest element after the array is sorted, not the kth different element.

Example 1:

Input: [3, 2, 1, 5, 6, 4] and k = 2
Output: 5

Example 2:

Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4
Output: 4

Explain:

You can assume that k is always valid and that 1 < k < array length

Answer Code

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(k > nums.size())
            return 0;
        k = nums.size() - k;

        quicksort(nums,0,nums.size()-1);
        return nums[k];

    }

public:
    void quicksort(vector<int>& arr,int l, int r){
        if(l >= r)
            return ;
        int mid;
        mid = partition(arr ,l ,r);
        quicksort(arr,l,mid-1);
        quicksort(arr,mid+1,r);
    }

public:
    //The key partitioning function ensures that the left side is smaller than the key and the right side is larger than the key.
    int partition(vector<int>& arr, int l ,int r){
      int  v = arr[l];//Baseline set to the first element

      //arr[l+1...j] < v arr[j+1 ... r] > v
      int j = l;
      for(int i = l + 1; i <= r; i++){ //It's important to understand why we start with L + 1, because we need to maintain the loop invariant arr [l + 1... j] < v.
          if(arr[i] < v){
              swap(arr[++j],arr[i]);
          }
      }
      swap(arr[l],arr[j]);
        return  j;
    }

};

Test code

#include <iostream>
#include <vector>

using namespace std;
//Using Quick Sorting Thought

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        if(k > nums.size())
            return 0;
        k = nums.size() - k;

        quicksort(nums,0,nums.size()-1);
        return nums[k];

    }

public:
    void quicksort(vector<int>& arr,int l, int r){
        if(l >= r)
            return ;
        int mid;
        mid = partition(arr ,l ,r);
        quicksort(arr,l,mid-1);
        quicksort(arr,mid+1,r);
    }

public:
    //The key partitioning function ensures that the left side is smaller than the key and the right side is larger than the key.
    int partition(vector<int>& arr, int l ,int r){
      int  v = arr[l];//Baseline set to the first element

      //arr[l+1...j] < v arr[j+1 ... r] > v
      int j = l;
      for(int i = l + 1; i <= r; i++){ //It's important to understand why we start with L + 1, because we need to maintain the loop invariant arr [l + 1... j] < v.
          if(arr[i] < v){
              swap(arr[++j],arr[i]);
          }
      }
      swap(arr[l],arr[j]);
        return  j;
    }

};

int main() {
    int n;
    cin>>n;
    int arr[n];
    for(int i = 0; i < n; i++)
        cin>>arr[i];
    vector<int> vec(arr,arr+ sizeof(arr)/ sizeof(int));
    cout<<Solution().findKthLargest(vec,n-1)<<endl;
    return 0;
}
Is this the world of the strong?

Welcome to the discussion, brush the topic together, and go to the world of the strong. CSDN@anchuanxu Jianjian Folding Villa

Posted on Wed, 09 Oct 2019 00:57:37 -0700 by JJohnsenDK