leetcode

commit 50c7d1e8e5143091fcf96f1a34d3510db621355c
parent cf1189cc092fdcbcac692029e234be4ff060bcb2
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Sun,  9 Apr 2023 20:11:10 -0500

Completed kth largest problem using count sort and quicksort

Diffstat:
A
kth-largest-element/a.out
 | 
0

A
kth-largest-element/kth-largest-element.cpp
 | 
24
++++++++++++++++++++++++
A
kth-largest-element/kth-largest-elementV2.cpp
 | 
49
+++++++++++++++++++++++++++++++++++++++++++++++++

3 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/kth-largest-element/a.out b/kth-largest-element/a.out
Binary files differ.
diff --git a/kth-largest-element/kth-largest-element.cpp b/kth-largest-element/kth-largest-element.cpp
@@ -0,0 +1,24 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+using namespace std;
+//Simple solution that has O(nlog(n)) complexity using built in sort.
+
+
+//Leet Ratings
+//       Speed  Memory
+//Total  99ms   45.4MB    
+//Beats  88.33% 73.57%
+
+int findKthLargest(vector<int>& nums, int k) {
+    sort(nums.begin(), nums.end());
+    return nums[nums.size() - k];
+}
+
+
+
+int main(){
+    vector<int> input_vec = {0, 1, 2, 4, 5, 6, 7,7 ,8, 9, 9, 9};
+    cout << findKthLargest(input_vec, 3) << endl;
+    return 0;
+}
diff --git a/kth-largest-element/kth-largest-elementV2.cpp b/kth-largest-element/kth-largest-elementV2.cpp
@@ -0,0 +1,49 @@
+#include <iostream>
+#include <vector>
+#include <algorithm>
+using namespace std;
+//This is my solution using custom count sort to be faster than quicksort (default sort)
+
+
+//Leet Ratings
+//       Speed Memory
+//Total  81ms  46.3MB    
+//Beats  96.3% 53.25%
+
+
+int findKthLargest(vector<int>& nums, int k) {
+    int highest = nums[0];
+    int lowest = nums[0];
+    for(int i = 0 ; i < nums.size() ; ++i){
+        if(nums[i] > highest){
+            highest = nums[i];
+        }
+        else if(nums[i] < lowest){
+            lowest = nums[i];
+        }
+    }
+    int diff = (highest - lowest) + 1;
+    vector<int> vec(diff , 0);
+    for(int i = 0 ; i < nums.size() ; ++i){
+        vec[nums[i] - lowest] =  vec[nums[i] - lowest] + 1;
+    }
+    int vals = 0;
+    for(int i = vec.size() - 1; i >= 0 ;  --i){
+        vals += vec[i];
+        if(vals >= k){
+            return i + lowest;
+        }
+    }
+    return 0;
+}
+
+
+
+
+
+
+int main(){
+    vector<int> input_vec = {0, 1, 2, 4, 5, 6, 7,7 ,8, 9, 9, 9};
+    cout << findKthLargest(input_vec, 3) << endl;
+    return 0;
+}