Sorting Problems on LeetCode
Table of Contents
- Kth Largest Element in an Array
① Bubble Sort (Time Limit Exceeded)
② C++ Standard Library Sorting Algorithm (std::sort):
③ Quick Sort (Time Limit Exceeded)
④ Improved Sorting Algorithm from Official Solusion:
⑤ Heap Sort
⑥ Bucket Sort
-
Top K Frequent Elements (No Idea at All)
-
Sort Characters By Frequency (Still Not Familiar with Hash Tables)
-
Sort Colors
Final Notes
215. Kth Largest Element in an Array
Since I have forgotten most of the sorting algorithms, I only remember bubble sort. I used it to sort the array in descending order and then returned nums[k-1], but some test cases exceeded the time limit.
① Bubble Sort (Time Limit Exceeded)
Bubble sort has a time complexity of O(n²), which is not suitable for this problem, so other algorithms or approaches are needed.
② C++ Standard Library Sorting Algorithm (std::sort):
You can directly use the sorting algorithm from the C++ standard library (such as std::sort) to sort the array. However, this approach might not be meaningful for practice purposes.
③ Quick Sort (Time Limit Exceeded)
// Quick Sort Algorithm
class Solution {
public:
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) {
return;
}
int key = nums[left];
int i = left, j = right;
while (i < j) {
while (nums[j] >= key && i < j) {
j--;
}
if (i < j) {
nums[i] = nums[j];
i++;
}
while (nums[i] <= key && i < j) {
i++;
}
if (i < j) {
nums[j] = nums[i];
j--;
}
}
nums[i] = key;
quickSort(nums, left, i - 1);
quickSort(nums, i + 1, right);
}
int findKthLargest(vector<int>& nums, int k) {
int right = nums.size();
quickSort(nums, 0, right - 1);
return nums[right - k];
}
};
④ Improved Sorting Algorithm from Official Solution:
This method divides the array during the sorting process. If the index i matches the target index, it returns nums[i]. Otherwise, it recurses into either the left or right subarray, improving efficiency. This method does not exceed the time limit but beats only 5.09% of submissions.
// Improved Quick Sort Method (Ascending)
class Solution {
public:
int quickSort(vector<int>& nums, int left, int right, int k) {
if (left == right) {
return nums[k];
}
int key = nums[left];
int i = left, j = right;
while (i != j) {
while (nums[j] >= key && i < j) {
j--;
}
if (i < j) {
nums[i] = nums[j];
i++;
}
while (nums[i] <= key && i < j) {
i++;
}
if (i < j) {
nums[j] = nums[i];
j--;
}
}
nums[i] = key;
if (k < i) {
return quickSort(nums, left, i - 1, k);
} else if (k == i) {
return nums[i];
} else {
return quickSort(nums, i + 1, right, k);
}
}
int findKthLargest(vector<int>& nums, int k) {
int right = nums.size() - 1;
return quickSort(nums, 0, right, right + 1 - k);
}
};
⑤ Heap Sort
Heap sort consists of two steps: building the initial heap and sorting (rebuilding the heap after swapping nodes).
// Heap Sort
class Solution {
public:
void heapify(vector<int>& nums, int len, int i) {
int maxIndex = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < len && nums[left] > nums[maxIndex]) {
maxIndex = left;
}
if (right < len && nums[right] > nums[maxIndex]) {
maxIndex = right;
}
if (maxIndex != i) {
swap(nums[i], nums[maxIndex]);
heapify(nums, len, maxIndex);
}
}
void heapSort(vector<int>& nums) {
int len = nums.size();
for (int i = len / 2 - 1; i >= 0; i--) {
heapify(nums, len, i);
}
for (len = len - 1; len >= 0; len--) {
swap(nums[len], nums[0]);
heapify(nums, len, 0);
}
}
int findKthLargest(vector<int>& nums, int k) {
heapSort(nums);
return nums[nums.size() - k];
}
};
⑥ Bucket Sort
The number of buckets is set manually, and each bucket's size is dynamic. The range of data each bucket can hold is calculated using buckSize.
// Bucket Sort
class Solution {
public:
void bucketSort(vector<int>& nums, int buckCount) {
if (nums.size() == 0 || buckCount <= 0) {
return;
}
int min = *min_element(nums.begin(), nums.end());
int max = *max_element(nums.begin(), nums.end());
int buckSize = (max - min) / buckCount + 1;
vector<vector<int>> buckets(buckCount);
for (int num : nums) {
int buckIndex = (num - min) / buckSize;
buckets[buckIndex].push_back(num);
}
nums.clear();
for (vector<int>& bucket : buckets) {
sort(bucket.begin(), bucket.end());
nums.insert(nums.end(), bucket.begin(), bucket.end());
}
}
int findKthLargest(vector<int>& nums, int k) {
int buckCount = 3;
bucketSort(nums, buckCount);
return nums[nums.size() - k];
}
};
347. Top K Frequent Elements (No Idea at All)
Given an integer array nums and an integer k, return the elements with the top k frequencies. You can return the answer in any order. The time complexity must be better than O(n log n) where n is the size of the array.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Official solution:
class Solution {
public:
static bool cmp(pair<int, int>& m, pair<int, int>& n) {
return m.second > n.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int, int> occurrences;
for (auto& num : nums) {
occurrences[num]++;
}
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> q(cmp);
for (auto& [num, count] : occurrences) {
if (q.size() == k) {
if (q.top().second < count) {
q.pop();
q.emplace(num, count);
}
} else {
q.emplace(num, count);
}
}
vector<int> ret;
while (!q.empty()) {
ret.emplace_back(q.top().first);
q.pop();
}
return ret;
}
};
Code explanation:
unordered_map overview:
unordered_map is a container in the C++ STL that is implemented based on a hash table, providing average O(1) time complexity for insertion, deletion, and lookup operations. Unlike map, unordered_map does not guarantee element ordering. unordered_map<int, int> occurrences; declares a hash table named occurrences where both keys and values are of type int.
occurrences[num]++ updates the hash table based on the current integer num. If num is not present in the hash table, it inserts a new key-value pair {num, 1}. If num is already in the hash table, the corresponding value (frequency) is incremented.
Priority Queue Overview:
priority_queue is a container adapter in the C++ standard library, typically used to implement a max-heap or min-heap. By default, it implements a max-heap, meaning the top element of the queue is always the highest-priority element (the largest value).
Regarding this code:
for (auto& [num, count] : occurrences) {
if (q.size() == k) {
if (q.top().second < count) {
q.pop();
q.emplace(num, count);
}
} else {
q.emplace(num, count);
}
}
Why is it q.top().second instead of q.second?
qis a priority queue (priority_queue), not a pair.q.top()returns the top element of the priority queue, which is apair<int, int>.q.top().secondaccesses the second element of this pair, which is the frequency.
The final part of the code retrieves elements from the priority queue q, storing each element's first value (the number) in the ret vector, and removing the element from the priority queue. Finally, this code builds a vector ret containing all the numbers from the priority queue.
451. Sort Characters By Frequency (Still Not Familiar with Hash Tables)
Given a string s, sort it in descending order based on the frequency of characters. A character's frequency is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any one of them. s consists of uppercase and lowercase English letters and digits.
Example 1:
Input: s = "tree"
Output: "eert"
Explanation: 'e' appears twice, 'r' and 't' appear once. So 'e' must come before 'r' and 't'. Also, "eetr" is a valid answer.
Example 2:
Input: s = "cccaaa"
Output: "cccaaa"
Explanation: 'c' and 'a' both appear three times. Also, "aaaccc" is a valid answer.
Note: "cacaca" is invalid because the same letters must be together.
Solution idea: I had no idea, so I copied the official solution.
Code:
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int len = s.length();
int maxfre = 0;
for (char c : s) {
mp[c]++;
maxfre = max(maxfre, mp[c]);
}
vector<string> buckets(maxfre + 1);
for (auto [c, num] : mp) {
buckets[num].push_back(c);
}
string ret;
for (int i = maxfre; i > 0; i--) {
string &bucket = buckets[i];
for (char c : bucket) {
for (int k = 0; k < i; k++) {
ret.push_back(c);
}
}
}
return ret;
}
};
75. Sort Colors
Given an array nums containing n elements, which are red, white, and blue, sort them in-place such that elements of the same color are adjacent, and they follow the order red, white, blue. Use integers 0, 1, and 2 to represent red, white, and blue respective. Solve this without using the built-in sort function.
Advanced: Can you think of a single-pass algorithm that uses constant space?
Example 1:
Input: nums = [2,0,2,1,1,0] Output: [0,0,1,1,2,2]Example 2:
Input: nums = [2,0,1] Output: [0,1,2]
Solution idea: Because of the previous question, I first thought of using bucket sort, storing 0, 1, and 2 in their respective buckets and then outputting the data from the buckets. But this is not in-place sorting. Which sorting method is in-place? Insertion sort? It doesn't matter, I'll try it.
class Solution {
public:
void sortColors(vector<int>& nums) {
int len = nums.size();
for (int i = 1; i < len; i++) {
int key = nums[i];
int j = i - 1;
while (j >= 0 && key < nums[j]) {
nums[j + 1] = nums[j];
j--;
}
nums[j + 1] = key;
}
}
};
Why is this question considered medium? It seems simpler than the previous one. After checking the solution, insertion sort traverses the array more then once, and there is a simpler method.
Final Notes
Sorting problems are temporarily concluded. There are still many issues to review.
