9.sort_ideas_leetcode.md

class Solution {
public:
    // 计数排序！因为给定了数据范围是1000
    #define MAX_N 1000
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int cnt[MAX_N + 5] = {0};
        // 初始化cnt
        // 这样只用正序遍历cnt就能知道每个数放在哪个位置了
        for (auto x : arr1) {
            cnt[x] += 1;
        }
        // k记录当前arr1数组中有多少元素
        int k = 0;
        // 按照arr2的顺序获取每个位子上元素的个数
        // 放到arr1里
        for (auto x : arr2) {
            for (int i = 0; i < cnt[x]; i++) {
                arr1[k++] = x;
            }
            cnt[x] = 0;
        }
        // 处理arr1多出来的元素
        for (int i = 0; i < MAX_N + 1; i++) {
            if (cnt[i] == 0) continue;
            for (int j = 0; j < cnt[i]; j++) arr1[k++] = i;
        }
        return arr1;
    }
};

但是代码还可以更简洁

class Solution {
public:
    #define MAX_N 1000
    vector<int> relativeSortArray(vector<int>& arr1, vector<int>& arr2) {
        int cnt[MAX_N + 5] = {0};
        for (auto x : arr1) {
            cnt[x] += 1;
        }
        int k = 0;
        for (auto x : arr2) {
            // 把 for 循环改写成 while循环
            // cnt[x]-- 和
            while (cnt[x]--) arr1[k++] = x;
        }
        for (int i = 0; i < MAX_N + 1; i++) {
            if (cnt[i] <= 0) continue;
            while(cnt[i]--) arr1[k++] = i;
        }
        return arr1;
    }
};

class Solution {
public:
    // 「线性时间」内运行并使用「线性额外空间」的算法。
    // 快排可不是O(n)
    // 并且数据范围太大了！不能用计数
    // 只能用基数了
    #define LOW 0xffff
    #define HIGH 0xffff0000
    #define MAX_N 65536
    
    #define LOW16(a) ((a) & LOW)
    #define __HIGH16(a) (((a) & 0xffff0000) >> 16)
    #define HIGH16(a) (__HIGH16(a) > INT16_MAX ? (__HIGH16(a) - 32768) : (__HIGH16(a) + 32768))
    
    int maximumGap(vector<int>& nums) {
        int cnt[MAX_N] = {0};
        vector<int>temp (nums.size());
        // 处理LOW16位
        for (auto x : nums) cnt[LOW16(x)] += 1;
        for (int i = 1; i < MAX_N; i++) cnt[i] += cnt[i - 1];
        for (int i = nums.size() - 1; i >= 0; --i) temp[--cnt[LOW16(nums[i])]] = nums[i];
        memset(cnt, 0, sizeof(cnt));
        // 处理高16
        for (auto x : temp) cnt[HIGH16(x)] += 1;
        for (int i = 1; i < MAX_N; i++) cnt[i] += cnt[i - 1];
        for (int i = temp.size() - 1; i >= 0; --i) nums[--cnt[HIGH16(temp[i])]] = temp[i];
        int ans = 0;
        for (int i = 1; i < nums.size(); i++) {
            ans = max(ans, nums[i] - nums[i - 1]);
        }
        return ans;
    }
};

class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(), citations.end());
        int h = 1, n = citations.size();
        while (h <= n && citations[n - h] >= h) ++h;
        h -= 1;
        return h;
    }
};

---

拓扑排序

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        // 有向图有环就没法完成课程的学习
        // 求有向图的拓扑序列
        // 如果序列长度 == 课程总数就能学完！

        int indeg[numCourses];
        memset(indeg, 0, sizeof(indeg));
        // 每个点指向的其他点的集合
        vector<vector<int>> g(numCourses);
        queue<int> q;
        for (auto x : prerequisites) {
            // x[1]->x[0]
            indeg[x[0]] += 1;
            g[x[1]].push_back(x[0]);
        }
        // 初始化已完成
        // 将入度 = 0的节点入队列
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.push(i);
        }
        // cnt 记录队列进入了多少节点
        // 也就是拓扑序中的节点
        int cnt = 0;
        while (!q.empty()) {
            int ind = q.front();
            q.pop();
            cnt += 1;
            // ind指向的全部节点的入度 - 1
            // 并且入度为0压入队列
            // 因为如果有环的话是就永远都会有入度不为0的点
            for (auto x : g[ind]) {
                indeg[x] -= 1;
                if (indeg[x] == 0) q.push(x);
            }
        }
        return cnt == numCourses;
    }
};

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        int indeg[numCourses];
        memset(indeg, 0, sizeof(indeg));
        vector<vector<int>> g(numCourses);
        queue<int> q;
        for (auto x : prerequisites) {
            indeg[x[0]] += 1;
            g[x[1]].push_back(x[0]);
        }
        for (int i = 0; i < numCourses; i++) {
            if (indeg[i] == 0) q.push(i);
        }
        vector<int> ans;
        int cnt = 0;
        while (!q.empty()) {
            int ind = q.front();
            q.pop();
            // 其实pop出去的就是拓扑序列了
            // 输出一下发现没问题
            // 直接猥琐一下push到数组中
            cout << "pop " << ind << endl;
            ans.push_back(ind);
            cnt += 1;
            for (auto x : g[ind]) {
                indeg[x] -= 1;
                if (indeg[x] == 0) q.push(x);
            }
        }
        return ans.size() == numCourses ? ans : vector<int>();
    }
};

class Solution {
public:
    // 对于[[1,3],[2,6],[8,10],[15,18]]
    // 每个左端点变成[x, +1] 右端点变成[y, -1]
    // 再push进新的数组 
    // [1, 1], [3, -1], [2, 1], [6, -1]
    // 我们按照端点从小到大的顺序遍历
    // 到6的时候 x.second == 0 即为新的区间

    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> arr;
        vector<int> temp(2);
        for (auto x : intervals) {
            temp[0] = x[0];
            temp[1] = 1;
            arr.push_back(temp);
            temp[0] = x[1];
            temp[1] = -1;
            arr.push_back(temp);
        }
        sort(arr.begin(), arr.end(), 
            [](const vector<int> &a, const vector<int> &b) -> bool {
                if (a[0] - b[0]) return a[0] < b[0];
                return a[1] > b[1];
            }
        );
        vector<vector<int>> ret;
        int pre = -1, sum = 0;
        for (int i = 0; i < arr.size(); i++) {
            if (pre == -1) pre = arr[i][0];
            sum += arr[i][1];
            if (sum == 0) {
                temp[0] = pre;
                temp[1] = arr[i][0];
                ret.push_back(temp);
                pre = -1;
            }
        }
        return ret;
    }
};