【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<Integer> l1 = new ArrayList();List<Integer> l2 = new ArrayList();l1.add(nums[0]);l2.add(nums[1]);for(int i=2; i<n; 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<l1.size(); i++) {res[idx] = l1.get(i);idx ++;}for(int i=0; i<l2.size(); i++) {res[idx] = l2.get(i);idx ++;}return res;}
}

3070. 元素和小于等于 k 的子矩阵的数目

给你一个下标从 0 开始的整数矩阵 grid 和一个整数 k。

返回包含 grid 左上角元素、元素和小于或等于 k 的 子矩阵 的
数目
。

---

思路：二维数组前缀和
复杂度：O（N*N）

class Solution {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<m; i++) {int s = 0;for(int j=0; j<n; 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] <= k) {ans ++;}}}return ans;}
}

3071. 在矩阵上写出字母 Y 所需的最少操作次数

给你一个下标从 0 开始、大小为 n x n 的矩阵 grid ，其中 n 为奇数，且 grid[r][c] 的值为 0 、1 或 2 。

如果一个单元格属于以下三条线中的任一一条，我们就认为它是字母 Y 的一部分：

从左上角单元格开始到矩阵中心单元格结束的对角线。
从右上角单元格开始到矩阵中心单元格结束的对角线。
从中心单元格开始到矩阵底部边界结束的垂直线。
当且仅当满足以下全部条件时，可以判定矩阵上写有字母 Y ：

属于 Y 的所有单元格的值相等。
不属于 Y 的所有单元格的值相等。
属于 Y 的单元格的值与不属于Y的单元格的值不同。
每次操作你可以将任意单元格的值改变为 0 、1 或 2 。返回在矩阵上写出字母 Y 所需的 最少 操作次数。

---

思路：数组y记录Y内区域每种元素出现次数，数组ny记录Y外区域每种元素出现次数。则所求问题即为求nn-y[i]-ny[j]的最小值，其中i与j不相等。
复杂度：O（NN）

class Solution {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<=n/2; i++) {vis[i][i] = true;}int idx = n/2;for(int j=n/2; j<n; j++) {vis[idx][j] = true;idx --;}idx = n/2;for(int i=n/2; i<n; i++) vis[i][idx]=true;for(int i=0; i<n; i++) {for(int j=0; j<n; j++) {if(vis[i][j]) {y[grid[i][j]] ++;} else {ny[grid[i][j]] ++;}}}// for(int i=0; i<n; i++) {//     for(int j=0; j<n; j++) {//         System.out.print(vis[i][j] +" ");//     }//     System.out.println(" ");// }
//         // for(int j=0; j<3; j++) {//      System.out.print(y[j] +" ");//  }int ans = n*n;for(int i=0; i<3; i++) {for(int j=0; j<3; 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;}
}

3072. 将元素分配到两个数组中 II

现定义函数 greaterCount ，使得 greaterCount(arr, val) 返回数组 arr 中 严格大于 val 的元素数量。

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

如果 greaterCount(arr1, nums[i]) > greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr1 。
如果 greaterCount(arr1, nums[i]) < greaterCount(arr2, nums[i]) ，将 nums[i] 追加到 arr2 。
如果 greaterCount(arr1, nums[i]) == greaterCount(arr2, nums[i]) ，将 nums[i] 追加到元素数量较少的数组中。
如果仍然相等，那么将 nums[i] 追加到 arr1 。
连接数组 arr1 和 arr2 形成数组 result 。例如，如果 arr1 == [1,2,3] 且 arr2 == [4,5,6] ，那么 result = [1,2,3,4,5,6] 。

返回整数数组 result 。

---

思路：树型数组。先将数组排序，用排序后的数组的序号来缩小数据范围。树型数组的[1,i]表示小于等于i的数量，则gc=n-sum[1,i]
复杂度：O（NlogN）

class Fenwick {public final int[] tree;public Fenwick(int n) {tree = new int[n];}public void add(int idx) {while(idx<tree.length) {tree[idx] ++;idx += idx & -idx;}}public int sum(int i) {int res =0;while(i>0) {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<Integer> a = new ArrayList();List<Integer> b = new ArrayList();a.add(nums[0]);b.add(nums[1]);ta.add(Arrays.binarySearch(sorted, nums[0])+1);tb.add(Arrays.binarySearch(sorted, nums[1])+1);for(int i=2; i<n; i++) {// 找到对应的映射int v1 = Arrays.binarySearch(sorted, nums[i]) +1;int gc1 = a.size() - ta.sum(v1);int gc2 = b.size() - tb.sum(v1);if(gc1>gc2 || gc1==gc2 && a.size()<=b.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<n; i++) {res[i] = a.get(i);}return res;}
}