leetcode

Leetcode submissions
git clone git://git.laack.co/leetcode.git
Log | Files | Refs | README

kth-largest-elementV2.cpp (1060B)

      1 #include <iostream>
      2 #include <vector>
      3 #include <algorithm>
      4 using namespace std;
      5 //This is my solution using custom count sort to be faster than quicksort (default sort)
      6 
      7 
      8 //Leet Ratings
      9 //       Speed Memory
     10 //Total  81ms  46.3MB    
     11 //Beats  96.3% 53.25%
     12 
     13 
     14 int findKthLargest(vector<int>& nums, int k) {
     15     int highest = nums[0];
     16     int lowest = nums[0];
     17     for(int i = 0 ; i < nums.size() ; ++i){
     18         if(nums[i] > highest){
     19             highest = nums[i];
     20         }
     21         else if(nums[i] < lowest){
     22             lowest = nums[i];
     23         }
     24     }
     25     int diff = (highest - lowest) + 1;
     26     vector<int> vec(diff , 0);
     27     for(int i = 0 ; i < nums.size() ; ++i){
     28         vec[nums[i] - lowest] =  vec[nums[i] - lowest] + 1;
     29     }
     30     int vals = 0;
     31     for(int i = vec.size() - 1; i >= 0 ;  --i){
     32         vals += vec[i];
     33         if(vals >= k){
     34             return i + lowest;
     35         }
     36     }
     37     return 0;
     38 }
     39 
     40 
     41 
     42 
     43 
     44 
     45 int main(){
     46     vector<int> input_vec = {0, 1, 2, 4, 5, 6, 7,7 ,8, 9, 9, 9};
     47     cout << findKthLargest(input_vec, 3) << endl;
     48     return 0;
     49 }