365 day challenge leetcode 1000 questions - day 035 one question per day + two point search 13

---

1260. Two dimensional grid migration

First brush self solution

class Solution {
    
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& grid, int k) {
    
        int m = grid.size();
        int n = grid[0].size();
        k %= m * n;
        for (int i = 0; i < k; i++) {
    
            int tmp = grid[m - 1][n - 1];
            for (int j = m - 1; j >= 0; j--) {
    
                for (int k = n - 1; k >= 0; k--) {
    
                    if (j == 0 && k == 0) break;
                    if (k == 0) grid[j][k] = grid[j - 1][n - 1];
                    else grid[j][k] = grid[j][k - 1];
                }
            }
            grid[0][0] = tmp;
        }
        return grid;
    }
};

Algorithm complexity ：$O(i\ast m\ast n)$, among i yes k modulus m*n
A better method is one-dimensional expansion , Calculate the next location of the element

528. Choose randomly by weight

First brush self solution

class Solution {
    
public:
    int sums;
    vector<int> prefix;
    Solution(vector<int>& w) {
    
        sums = 0;
        for (const auto& weight : w) {
    
            sums += weight;
            prefix.push_back(sums);
        }
    }
    
    int pickIndex() {
    
        int random = rand() % sums + 1;
        auto it = lower_bound(prefix.begin(), prefix.end(), random);
        return it - prefix.begin();
    }
};

/** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(w); * int param_1 = obj->pickIndex(); */

Algorithm complexity ：$O(n+k\ast log(n))$,k Is to call pickIndex() The number of times