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

本文主要是介绍LeetCode-day03-3072. 将元素分配到两个数组中 II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

题目描述
示例
- 示例1：
- 示例2：
- 示例3：
思路
代码

题目描述

给你一个下标从 1 开始、长度为 n 的整数数组 nums 。

现定义函数 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：

输入：nums = [2,1,3,3]
输出：[2,3,1,3]
解释：在前两次操作后，arr1 = [2] ，arr2 = [1] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是零，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4次操作中，两个数组中大于 3 的元素数量都是零，但 arr2 的长度较小，因此，将 nums[4] 追加到 arr2 。
在 4次操作后，arr1 = [2,3] ，arr2 = [1,3] 。
因此，连接形成的数组 result 是 [2,3,1,3] 。

示例2：

输入：nums = [5,14,3,1,2]
输出：[5,3,1,2,14]
解释：在前两次操作后，arr1 = [5] ，arr2 = [14] 。
在第 3 次操作中，两个数组中大于 3 的元素数量都是一，并且长度相等，因此，将 nums[3] 追加到 arr1 。
在第 4 次操作中，arr1 中大于 1 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[4] 追加到 arr1 。
在第 5 次操作中，arr1 中大于 2 的元素数量大于 arr2 中的数量（2 > 1），因此，将 nums[5] 追加到 arr1 。
在 5 次操作后，arr1 = [5,3,1,2] ，arr2 = [14] 。
因此，连接形成的数组 result 是 [5,3,1,2,14] 。

示例3：

输入：nums = [3,3,3,3]
输出：[3,3,3,3]
解释：在 4 次操作后，arr1 = [3,3] ，arr2 = [3,3] 。
因此，连接形成的数组 result 是 [3,3,3,3] 。

思路

数组元素数量比较，查找时使用二分查找，否则会超时！

代码

 public static int[] resultArray(int[] nums) {List<Integer> arr1 = new ArrayList<>();List<Integer> arr11 = new ArrayList<>();List<Integer> arr2 = new ArrayList<>();List<Integer> arr22 = new ArrayList<>();for (int e : nums) {if (arr1.isEmpty()) {arr1.add(e);arr11.add(e);continue;}if (arr2.isEmpty()) {arr2.add(e);arr22.add(e);continue;}int idx1 = binarySearch(arr1, e + 1);int idx2 = binarySearch(arr2, e + 1);int cnt1 = arr1.size() - idx1;int cnt2 = arr2.size() - idx2;if (cnt1 > cnt2) {arr1.add(idx1, e);arr11.add(e);continue;}if (cnt1 < cnt2) {arr2.add(idx2, e);arr22.add(e);continue;}if (cnt1 == cnt2) {if (arr1.size() <= arr2.size()) {arr1.add(idx1, e);arr11.add(e);} else {arr2.add(idx2, e);arr22.add(e);}}}List<Integer> result = new ArrayList<>(arr11);result.addAll(arr22);// 将结果列表转换为数组int[] resultArray = new int[result.size()];for (int i = 0; i < result.size(); i++) {resultArray[i] = result.get(i);}return resultArray;}public static int binarySearch(List<Integer> arr, int target) {int low = 0, high = arr.size();while (low < high) {int mid = (low + high) / 2;if (arr.get(mid) < target) {low = mid + 1;} else {high = mid;}}return low;}