Algorithms & Data Structures : Sorting Problems

Problem

LeetCode 215. Kth Largest Element in an Array

LeetCode 2279. Maximum Bags With Full Capacity of Rocks
[sorting][greedy]

LeetCode : 786. K-th Smallest Prime Fraction
[sorting][binary search][priority queue]

LeetCode : 2054. Two Best Non-Overlapping Events
[Sorting][Ordered Map][Binary Search][Dynamic Programming][Priority Queue]

LeetCode : 1984. Minimum Difference Between Highest and Lowest of K Scores
[Array][Sorting][Sliding Window]

LeetCode : 2357. Make Array Zero by Subtracting Equal Amounts
[sorting][hash table][priority queue]

LeetCode : 2231. Largest Number After Digit Swaps by Parity
[Sorting][Heap ( Priority Queue)]

LeetCode : 2136. Earliest Possible Day of Full Bloom
[Sorting][Greedy][Hard]

—

LeetCode 912. Sort an Array

LeetCode 215. Kth Largest Element in an Array

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - k];
    }
};

LeetCode 2279. Maximum Bags With Full Capacity of Rocks

class Solution {
public:
    int maximumBags(vector<int>& capacity, vector<int>& rocks, int additionalRocks) {
        vector<int> diff = vector<int>(rocks.size());
        
        for(int i = 0;i < rocks.size();i++) {
            diff[i] = capacity[i] - rocks[i];
        } 
        
        sort(diff.begin(), diff.end());
        
        int ans = 0;
        for(int i = 0;i < diff.size();i++) {
            if(additionalRocks < diff[i]) {
                break;
            }
            ans++;
            additionalRocks -= diff[i];
        }
        
        return ans;
    }
};

LeetCode : 786. K-th Smallest Prime Fraction

// TODO : 壓低複雜度
typedef struct Node Node;
struct Node {
    double d;
    int n1;
    int n2;
};
class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {      
        vector<Node> dv;
        
        for(int i = 0;i < arr.size();i++) {
            for(int j = i + 1;j < arr.size();j++) {
                double tmp = (double)arr[i] / arr[j];
                dv.push_back({tmp, arr[i], arr[j]});
            }
        }
        
        sort(dv.begin(), dv.end(), [](const Node & a, const Node & b) -> bool
        { 
            return a.d < b.d; 
        });
return {dv[k - 1].n1, dv[k - 1].n2};
    }
};

LeetCode : 2054. Two Best Non-Overlapping Events

// TODO : 效能太差了
bool cmpStart(vector<int> &a, vector<int> &b) {
    if(a[0] < b[0]) {
        return true;
    }
    return false;
}
bool cmpEnd(vector<int> &a, vector<int> &b) {
    if(a[1] < b[1]) {
        return true;
    }
    return false;
}
class Solution {
public:
    int maxTwoEvents(vector<vector<int>>& events) {
        vector<vector<int>> sortStart = events;
        vector<vector<int>> sortEnd = events;
        
        sort(sortStart.begin(), sortStart.end(), cmpStart);
        sort(sortEnd.begin(), sortEnd.end(), cmpEnd);
        
        map<int, int> m;
        int maxVal = INT_MIN;
        for(int i = sortStart.size() - 1;i >= 0;i--) {
            maxVal = max(maxVal, sortStart[i][2]);
            m[sortStart[i][0]] = maxVal;
        }
        m[1000000005] = 0;
        
        int ans = INT_MIN;
        for(int i = 0;i < sortEnd.size();i++) {
            int nowe = sortEnd[i][1];
            // printf("nowe : %d\n", nowe);
            auto it = m.upper_bound(nowe);
            ans = max(ans, sortEnd[i][2] + it->second);
        }
        
        return ans;
    }
};

LeetCode : 1984. Minimum Difference Between Highest and Lowest of K Scores

class Solution {
public:
    int minimumDifference(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        
        int ans = INT_MAX;
        for(int i = 0;i < nums.size() - (k - 1);i++) {
            ans = min(ans, abs(nums[i] - nums[i + (k - 1)]));
        }
        
        return ans;
    }
};

LeetCode : 2357. Make Array Zero by Subtracting Equal Amounts

class Solution {
public:
    int minimumOperations(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int nowm = -1;
        int num = 0;
        for(int i = 0;i < nums.size();i++) {
            if(nums[i] != 0) {
                if(nowm == -1) {
                    nowm = nums[i];
                    num++;
                } else if (nowm != nums[i]) {
                    nowm = nums[i];
                    num++;
                }
            }
        }
        return num;
    } 
};

LeetCode : 2231. Largest Number After Digit Swaps by Parity

class Solution {
public:
    int largestInteger(int num) {
        vector<int> nv;
        vector<int> even;
        vector<int> odd;
        int tmp = num;
        while(tmp > 0) {
            nv.push_back(tmp % 10);
            tmp /= 10;
        }

        for(int i = 0;i < nv.size();i++) {
            if(nv[i] % 2 == 0) {
                even.push_back(nv[i]);
            } else {
                odd.push_back(nv[i]);
            }
        }

        sort(even.begin(), even.end());
        sort(odd.begin(), odd.end());
        
        for(int i = nv.size() - 1;i >= 0;i--) {
            if(nv[i] % 2 == 0) {
                nv[i] = even.back();
                even.pop_back();
            } else {
                nv[i] = odd.back();
                odd.pop_back();
            }
        }

        int ans = 0;
        while(!nv.empty()) {
            ans *= 10;
            ans += nv.back();
            nv.pop_back();
        }

        return ans;
    }
};

LeetCode : 2136. Earliest Possible Day of Full Bloom

// TODO : 效能太差
// 最重要的是最後一個元素的 growTime
// plantTime 的和，就是至少要花多少時間
// G: 照著 growTime 排序，最尾端要是 growTime 最小的
// --> 應該是這樣做沒錯 ?
// 優化方案：自己實作 sort ， 當 growTime 更改排序方式時，也一併改變 plantTime 的排序方式
//          這樣就不需要再另外 push 到 tmp 這個 vector 裡面。
class Solution {
public:
    int earliestFullBloom(vector<int>& plantTime, vector<int>& growTime) {
        vector<vector<int>> tmp;
        for(int i = 0;i < growTime.size();i++) {
            tmp.push_back({growTime[i], plantTime[i]});
        }
        sort(tmp.begin(), tmp.end());
        int ans = 0;
        int nowlen = 0;
        for(int i = tmp.size() - 1;i >= 0;i--) {
            nowlen += tmp[i][1];
            ans = max(ans, nowlen + tmp[i][0]);
        }
        return ans;
    }
};