听寒's Blog

vector<int> nums; int n=nums.size();
for(int i=0; i<n; i++) {
    uniform_int_distribution<> dis(i, n-1);  // range is [i, n-1]
    int j=dis(gen);
    swap(nums[i], nums[j]);
} 
return nums;

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()==1) return;
        // find the largest index i which statisfies nums[i]<nums[i+1]
        // 从后往前找到交换点i，交换点i以后的数全部都是降序的
        // 因为i后面的数[i+1, n)已经无法变得更大，所以我们不得不让i位置变大一点来得到下一个序列
        int i=nums.size()-2;
        while(i>=0 && nums[i]>=nums[i+1]) {
            i--;
        }
        if(i<0) {
            // 如果找不到这么一个位置i，表示整个序列都是降序的，即已经是最后一个排列。
            // 重新得到第一个排列的方法是整个数组逆序。
            reverse(nums.begin(), nums.end());
            return;
        }
        // 可想而知，为了是变大程度尽量小，i前面的数不应该改动，我们从i后面的数里面挑出一个比i稍大的
        // 因为后面是降序，所以可以直接按位置查找
        // find the largest index j which statisfies nums[j]>nums[j]
        int j=nums.size()-1;
        while(nums[j] <= nums[i]) {
            j--;
        }
        // 我们将这个数nums[j]交换到nums[i]的位置
        swap(nums[i], nums[j]); 
        // 因为我们找到的nums[j]是比nums[i]刚刚稍小的数，所以交换完成后，后面的区间[i+1,n]仍然是降序的
        // 此时还没有结束。因为后面的区间[i+1,n]是降序的，我们知道降序是最大的排列（最后一个排列）而不是最小的排序
        // 我们将这个降序区间调整回为升序区间，此时才是下一个排列
        reverse(nums.begin()+i+1, nums.end());
    }
};

int maxSubArray(vector<int>& nums) {
    if(nums.empty()) return 0;
    size_t n=nums.size();
    vector<int> ans(n); // 代表以nums[i]为结尾的连续最大和
    ans[0]=nums[0];
    for(int i=1;i<n;i++) {
        ans[i]=max(ans[i-1]+nums[i],nums[i]);
    }
    return *max_element(ans.begin(), ans.end());
}

int maxCrossingSubArray(vector<int>& nums, int left, int mid, int right) {
    int leftSum=0;
    for(int i=mid-1, sum=0; i>=left; i--) {
        sum+=nums[i];
        if(sum > leftSum) {
            leftSum = sum;
        }
    }
    int rightSum=0;
    for(int i=mid+1, sum=0; i<=right; i++) {
        sum+=nums[i];
        if(sum > rightSum) {
            rightSum = sum;
        }
    }
    return leftSum+nums[mid]+rightSum;
}
int maxSubArray(vector<int>& nums, int left, int right) {
    if (left==right) {
        return nums[left]; // base case
    }
    int mid = (left+right)/2;
    int rLeft = maxSubArray(nums, left, mid);
    int rRight = maxSubArray(nums, mid+1, right);
    int rMid = maxCrossingSubArray(nums, left, mid, right);
    return max(max(rLeft, rRight), rMid);
}
int maxSubArray(vector<int>& nums) {
    return maxSubArray(nums, 0, nums.size()-1);
}

struct Status {
    int lSum, rSum, mSum, iSum;
};

Status pushUp(Status l, Status r) {
    int iSum = l.iSum + r.iSum;
    int lSum = max(l.lSum, l.iSum + r.lSum);
    int rSum = max(r.rSum, r.iSum + l.rSum);
    int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
    return (Status) {lSum, rSum, mSum, iSum};
};

Status get(vector<int> &a, int l, int r) {
    if (l == r) {
        return (Status) {a[l], a[l], a[l], a[l]};
    }
    int m = (l + r) >> 1;
    Status lSub = get(a, l, m);
    Status rSub = get(a, m + 1, r);
    return pushUp(lSub, rSub);
}

int maxSubArray(vector<int>& nums) {
    return get(nums, 0, nums.size() - 1).mSum;
}

class Solution {
public:
    inline int merge(vector<int>& nums, size_t p, size_t q, size_t r) {
        if(!(p<=q && q<r)) return 0;
        int numRev=0;
        size_t n1 = q-p+1, n2 = r-q;
        vector<int> A(n1), B(n2);
        for(size_t i=0;i<n1;i++) A[i]=nums[p+i];
        for(size_t i=0;i<n2;i++) B[i]=nums[q+1+i];
        size_t i=0, j=0;
        for(size_t c=p;c<=r;c++) {
            // 注意判定边界。
            // 另外不可以用哨兵值的方法，因为此题输入可能会包含int的最大值
            if (i>=n1) {
                // 左区间全部用完了，复制右区间
                nums[c] = B[j++];
                // 此处也不需要增加numRev，左侧已经用完，没有元素再与右侧构成逆序对，numRev增量必然是0
            } else if (j>=n2) {
                // 右区间全部用完了，复制左区间
                nums[c] = A[i++];
            } else {
                // 都没用完，正常对比
                if(A[i] <= B[j]) {
                    nums[c] = A[i++];
                } else {
                    nums[c] = B[j++];
                    //if (A[i] != B[j])
                    numRev += n1-i; // 左侧全部剩余元素A[i...n1]与右侧第一个剩余元素B[j]构成全部相关的逆序对
                }
            }
        }
        return numRev;
    }
    int solve(vector<int>& nums, int p, int r){
        if(p>=r) return 0;
        int q=(p+r)/2;
        int cnt=0;
        cnt+=solve(nums,p,q);   // 不要忘记加上子问题时发现的逆序对
        cnt+=solve(nums,q+1,r); // 不要忘记加上子问题时发现的逆序对
        cnt+=merge(nums,p,q,r); // 合并同时也求解本层上的逆序对
        return cnt;
    }
    int reversePairs(vector<int>& nums) {
        vector<int> copy(nums);
        return solve(copy, 0, nums.size()-1);
    }
};