【LeetCode】第 387 场周赛

3069. 将元素分配到两个数组中 I

���你一个下标从 1 开始、包含 不同 整数的数组 nums ，数组长度为 n 。

你需要通过 n 次操作，将 nums 中的所有元素分配到两个数组 arr1 和 arr2 中。在第一次操作中，将 nums[1] 追加到 arr1 。在第二次操作中，将 nums[2] 追加到 arr2 。之后，在第 i 次操作中：

如果 arr1 的最后一个元素 大于 arr2 的最后一个元素，就将 nums[i] 追加到 arr1 。否则，将 nums[i] 追加到 arr2 。

通过连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回数组 result 。

复杂度：O（N）

class Solution {    public int[] resultArray(int[] nums) {        int n = nums.length;        List l1 = new ArrayList();        List l2 = new ArrayList();        l1.add(nums[0]);        l2.add(nums[1]);        for(int i=2; i            int i1 = l1.size()-1;            int i2 = l2.size()-1;            if(l1.get(i1)  l2.get(i2)) {                l1.add(nums[i]);            } else {                l2.add(nums[i]);            }        }                int[] res = new int[n];        int idx = 0;        for(int i=0; i            res[idx] = l1.get(i);            idx ++;        }                for(int i=0; i            res[idx] = l2.get(i);            idx ++;        }        return res;            }}    public int countSubmatrices(int[][] grid, int k) {        int m = grid.length;        int n = grid[0].length;        int[][] dp = new int[m][n];        // dp[0][0] = grid[0][0];        int ans = 0;        for(int i=0; i            int s = 0;            for(int j=0; j                s = s + grid[i][j];                dp[i][j] = s;                if(i-1=0) {                    dp[i][j] += dp[i-1][j];                }                if(dp[i][j]                     ans ++;                }            }                    }        return ans;    }}    public int minimumOperationsToWriteY(int[][] grid) {        int n = grid.length;         int[] y = new int[3];        int[] ny = new int[3];        boolean[][] vis = new boolean[n][n];        for(int i=0; i            vis[i][i] = true;        }        int idx = n/2;        for(int j=n/2; j            vis[idx][j] = true;            idx --;        }        idx = n/2;        for(int i=n/2; i            for(int j=0; j                if(vis[i][j]) {                    y[grid[i][j]] ++;                } else {                    ny[grid[i][j]] ++;                }            }        }                // for(int i=0; i        //     for(int j=0; j        //         System.out.print(vis[i][j] +" ");        //     }        //     System.out.println(" ");        // }//                        // for(int j=0; j               //      System.out.print(y[j] +" ");               //  }        int ans = n*n;        for(int i=0; i            for(int j=0; j                if(i!=j){                 //   System.out.println(n*n-y[i]+ny[j]);                    ans = Math.min(ans, n*n-y[i]-ny[j]);                }             }        }        return ans;            }}    public final int[] tree;    public Fenwick(int n) {        tree = new int[n];    }    public void add(int idx) {        while(idx            tree[idx] ++;            idx += idx & -idx;        }    }    public int sum(int i) {        int res =0;        while(i0) {            res += tree[i];            i -= i& -i;        }        return res;    }}class Solution {    public int[] resultArray(int[] nums) {        int[] sorted = nums.clone();        Arrays.sort(sorted);        int n = nums.length;                Fenwick ta = new Fenwick(n+1);        Fenwick tb = new Fenwick(n+1);        List            // 找到对应的映射            int v1 = Arrays.binarySearch(sorted, nums[i]) +1;            int gc1 = a.size() - ta.sum(v1);            int gc2 = b.size() - tb.sum(v1);            if(gc1gc2 || gc1==gc2 && a.size()                a.add(nums[i]);                ta.add(v1);            } else {                b.add(nums[i]);                tb.add(v1);            }        }        for(int num:b) {           a.add(num);         }                int[] res = new int[n];        for(int i=0; i            res[i] = a.get(i);        }        return res;    }}