题目

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

思路

这里要我返回这个顺序递增的这个数组，最暴力就是平移+排序
然后我的思路是，你后面这个nums2, 他可以二分找到这个要插入的位置，然后这插入的这个位置是一个顺序set
对应每个nums2的元素都需要对nums1来进行二分，如果num1 n, nums2 m,那这里复杂度就是mlogn，然后这里我需要对每个插入的这些nums2的这些元素分别来做排序
也就是milogmi, sum mi = m;

每个桶大小 mi，排序 O(mi log mi)，总和 O(Σ mi log mi)，其中 Σmi = m
由于 Σ mi log mi ≤ m log m（当所有元素集中在一个桶时取等），所以排序部分上界是 O(m log m) 这部分我算不明白，总之这里放缩了
然后就总复杂度：O(m log n + m log m) = O(m log(mn))

但是这里有些边界条件，首先写个二分，如果这里mp[i]表示插入到num1[i]后的，那有可能找不到，那就是0，反之就是n，有些边界条件，估计要调试一会儿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if (n == 0) return;
        if (m == 0) { nums1 = nums2; return; }

        map<int, multiset<int>> mp;

        for (int i = 0; i < n; i++) {
            int num = nums2[i];
            // 找最后一个 <= num 的位置
            int l = 0, r = m - 1;
            while (l < r) {
                int mid = (l + r + 1) >> 1;
                if (nums1[mid] <= num) l = mid;
                else r = mid - 1;
            }
            if (nums1[l] <= num) {
                mp[l].insert(num);
            } else {
                // num 比 nums1[0] 还小，放在最前面
                mp[-1].insert(num);
            }
        }

        vector<int> tmp;
        for (auto& x : mp[-1]) tmp.push_back(x);
        for (int i = 0; i < m; i++) {
            tmp.push_back(nums1[i]);
            for (auto& x : mp[i]) tmp.push_back(x);
        }

        nums1 = tmp;
    }
};

然后实际上这个题最好的解法是双指针，就你搞个新的大数组对吧？然后他每次一定能从你这其他这俩数组塞一个进去，然后每次数组的index都能–，然后被塞的那个也能–，就逆序塞满了，还没有边界条件