class Solution {
public:
vector<int> resultArray(vector<int>& nums) {
}
};
100246. 将元素分配到两个数组中 II
给你一个下标从 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] 。
提示：
3 <= n <= 1051 <= nums[i] <= 109原站题解
java 解法, 执行用时: 75 ms, 内存消耗: 63 MB, 提交时间: 2024-06-05 09:59:45
class Fenwick {
private final int[] tree;
public Fenwick(int n) {
tree = new int[n];
}
// 把下标为 i 的元素增加 v
public void add(int i, int v) {
while (i < tree.length) {
tree[i] += v;
i += i & -i;
}
}
// 返回下标在 [1,i] 的元素之和
public int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
}
class Solution {
public int[] resultArray(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted); // 只排序不去重
int n = nums.length;
List<Integer> a = new ArrayList<>(n); // 预分配空间
List<Integer> b = new ArrayList<>();
a.add(nums[0]);
b.add(nums[1]);
Fenwick t = new Fenwick(n + 1);
t.add(n - Arrays.binarySearch(sorted, nums[0]), 1);
t.add(n - Arrays.binarySearch(sorted, nums[1]), -1);
for (int i = 2; i < nums.length; i++) {
int x = nums[i];
int v = n - Arrays.binarySearch(sorted, x);
int d = t.pre(v - 1); // 转换成 < v 的元素个数之差
if (d > 0 || d == 0 && a.size() <= b.size()) {
a.add(x);
t.add(v, 1);
} else {
b.add(x);
t.add(v, -1);
}
}
a.addAll(b);
for (int i = 0; i < n; i++) {
nums[i] = a.get(i);
}
return nums;
}
}
java 解法, 执行用时: 81 ms, 内存消耗: 63 MB, 提交时间: 2024-06-05 09:59:31
class Fenwick {
private final int[] tree;
public Fenwick(int n) {
tree = new int[n];
}
// 把下标为 i 的元素增加 1
public void add(int i) {
while (i < tree.length) {
tree[i]++;
i += i & -i;
}
}
// 返回下标在 [1,i] 的元素之和
public int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
}
class Solution {
public int[] resultArray(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted); // 只排序不去重
int n = nums.length;
List<Integer> a = new ArrayList<>(n); // 预分配空间
List<Integer> b = new ArrayList<>();
a.add(nums[0]);
b.add(nums[1]);
Fenwick t1 = new Fenwick(n + 1);
Fenwick t2 = new Fenwick(n + 1);
t1.add(Arrays.binarySearch(sorted, nums[0]) + 1);
t2.add(Arrays.binarySearch(sorted, nums[1]) + 1);
for (int i = 2; i < nums.length; i++) {
int x = nums[i];
int v = Arrays.binarySearch(sorted, x) + 1;
int gc1 = a.size() - t1.pre(v); // greaterCount(a, v)
int gc2 = b.size() - t2.pre(v); // greaterCount(b, v)
if (gc1 > gc2 || gc1 == gc2 && a.size() <= b.size()) {
a.add(x);
t1.add(v);
} else {
b.add(x);
t2.add(v);
}
}
a.addAll(b);
for (int i = 0; i < n; i++) {
nums[i] = a.get(i);
}
return nums;
}
}
cpp 解法, 执行用时: 226 ms, 内存消耗: 117.6 MB, 提交时间: 2024-06-05 09:59:01
class Fenwick {
vector<int> tree;
public:
Fenwick(int n) : tree(n) {}
// 把下标为 i 的元素增加 1
void add(int i) {
while (i < tree.size()) {
tree[i]++;
i += i & -i;
}
}
// 返回下标在 [1,i] 的元素之和
int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
};
class Solution {
public:
vector<int> resultArray(vector<int> &nums) {
auto sorted = nums;
ranges::sort(sorted);
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int m = sorted.size();
vector<int> a{nums[0]}, b{nums[1]};
Fenwick t1(m + 1), t2(m + 1);
t1.add(ranges::lower_bound(sorted, nums[0]) - sorted.begin() + 1);
t2.add(ranges::lower_bound(sorted, nums[1]) - sorted.begin() + 1);
for (int i = 2; i < nums.size(); i++) {
int x = nums[i];
int v = ranges::lower_bound(sorted, x) - sorted.begin() + 1;
int gc1 = a.size() - t1.pre(v); // greaterCount(a, v)
int gc2 = b.size() - t2.pre(v); // greaterCount(b, v)
if (gc1 > gc2 || gc1 == gc2 && a.size() <= b.size()) {
a.push_back(x);
t1.add(v);
} else {
b.push_back(x);
t2.add(v);
}
}
a.insert(a.end(), b.begin(), b.end());
return a;
}
};
cpp 解法, 执行用时: 198 ms, 内存消耗: 116 MB, 提交时间: 2024-06-05 09:58:52
class Fenwick {
vector<int> tree;
public:
Fenwick(int n) : tree(n) {}
// 把下标为 i 的元素增加 v
void add(int i, int v) {
while (i < tree.size()) {
tree[i] += v;
i += i & -i;
}
}
// 返回下标在 [1,i] 的元素之和
int pre(int i) {
int res = 0;
while (i > 0) {
res += tree[i];
i &= i - 1;
}
return res;
}
};
class Solution {
public:
vector<int> resultArray(vector<int> &nums) {
auto sorted = nums;
ranges::sort(sorted);
sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
int m = sorted.size();
vector<int> a{nums[0]}, b{nums[1]};
Fenwick t(m + 1);
t.add(sorted.end() - ranges::lower_bound(sorted, nums[0]), 1);
t.add(sorted.end() - ranges::lower_bound(sorted, nums[1]), -1);
for (int i = 2; i < nums.size(); i++) {
int x = nums[i];
int v = sorted.end() - ranges::lower_bound(sorted, x);
int d = t.pre(v - 1); // 转换成 < v 的元素个数之差
if (d > 0 || d == 0 && a.size() <= b.size()) {
a.push_back(x);
t.add(v, 1);
} else {
b.push_back(x);
t.add(v, -1);
}
}
a.insert(a.end(), b.begin(), b.end());
return a;
}
};
golang 解法, 执行用时: 196 ms, 内存消耗: 9.9 MB, 提交时间: 2024-03-06 10:00:09
type fenwick []int
// 把下标为 i 的元素增加 1
func (f fenwick) add(i int) {
for ; i < len(f); i += i & -i {
f[i]++
}
}
// 返回下标在 [1,i] 的元素之和
func (f fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += f[i]
}
return
}
func resultArray(nums []int) (ans []int) {
sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)
m := len(sorted)
a := nums[:1]
b := []int{nums[1]}
t1 := make(fenwick, m+1)
t2 := make(fenwick, m+1)
t1.add(sort.SearchInts(sorted, nums[0]) + 1)
t2.add(sort.SearchInts(sorted, nums[1]) + 1)
for _, x := range nums[2:] {
v := sort.SearchInts(sorted, x) + 1
gc1 := len(a) - t1.pre(v) // greaterCount(a, v)
gc2 := len(b) - t2.pre(v) // greaterCount(b, v)
if gc1 > gc2 || gc1 == gc2 && len(a) <= len(b) {
a = append(a, x)
t1.add(v)
} else {
b = append(b, x)
t2.add(v)
}
}
return append(a, b...)
}
golang 解法, 执行用时: 201 ms, 内存消耗: 10.5 MB, 提交时间: 2024-03-06 09:59:42
type fenwick []int
// 把下标为 i 的元素增加 v
func (f fenwick) add(i, v int) {
for ; i < len(f); i += i & -i {
f[i] += v
}
}
// 返回下标在 [1,i] 的元素之和
func (f fenwick) pre(i int) (res int) {
for ; i > 0; i &= i - 1 {
res += f[i]
}
return
}
func resultArray(nums []int) (ans []int) {
sorted := slices.Clone(nums)
slices.Sort(sorted)
sorted = slices.Compact(sorted)
m := len(sorted)
a := nums[:1]
b := []int{nums[1]}
t := make(fenwick, m+1)
t.add(m-sort.SearchInts(sorted, nums[0]), 1)
t.add(m-sort.SearchInts(sorted, nums[1]), -1)
for _, x := range nums[2:] {
v := m - sort.SearchInts(sorted, x)
d := t.pre(v - 1) // 转换成 < v 的元素个数之差
if d > 0 || d == 0 && len(a) <= len(b) {
a = append(a, x)
t.add(v, 1)
} else {
b = append(b, x)
t.add(v, -1)
}
}
return append(a, b...)
}
python3 解法, 执行用时: 807 ms, 内存消耗: 37.7 MB, 提交时间: 2024-03-06 09:59:08
# 一棵树状数组
class Fenwick:
__slots__ = 'tree'
def __init__(self, n: int):
self.tree = [0] * n
# 把下标为 i 的元素增加 v
def add(self, i: int, v: int) -> None:
while i < len(self.tree):
self.tree[i] += v
i += i & -i
# 返回下标在 [1,i] 的元素之和
def pre(self, i: int) -> int:
res = 0
while i > 0:
res += self.tree[i]
i &= i - 1
return res
class Solution:
def resultArray(self, nums: List[int]) -> List[int]:
sorted_nums = sorted(set(nums))
m = len(sorted_nums)
a = [nums[0]]
b = [nums[1]]
t = Fenwick(m + 1)
t.add(m - bisect_left(sorted_nums, nums[0]), 1)
t.add(m - bisect_left(sorted_nums, nums[1]), -1)
for x in nums[2:]:
v = m - bisect_left(sorted_nums, x)
d = t.pre(v - 1) # 转换成 < v 的元素个数之差
if d > 0 or d == 0 and len(a) <= len(b):
a.append(x)
t.add(v, 1)
else:
b.append(x)
t.add(v, -1)
return a + b
python3 解法, 执行用时: 932 ms, 内存消耗: 37.5 MB, 提交时间: 2024-03-06 09:58:27
'''
将元素离散化成[1, m]中的元素，其中m为nums中不同元素个数。
对nums排序去重后，在数组中二分查找得到；
用两棵树分别维护arr1和arr2中每个元素的出现次数，可快速计算出greaterCount
'''
class Fenwick:
__slots__ = 'tree'
def __init__(self, n: int):
self.tree = [0] * n
# 把下标为 i 的元素增加 1
def add(self, i: int) -> None:
while i < len(self.tree):
self.tree[i] += 1
i += i & -i
# 返回下标在 [1,i] 的元素之和
def pre(self, i: int) -> int:
res = 0
while i > 0:
res += self.tree[i]
i &= i - 1
return res
class Solution:
def resultArray(self, nums: List[int]) -> List[int]:
sorted_nums = sorted(set(nums))
m = len(sorted_nums)
a = [nums[0]]
b = [nums[1]]
t1 = Fenwick(m + 1)
t2 = Fenwick(m + 1)
t1.add(bisect_left(sorted_nums, nums[0]) + 1)
t2.add(bisect_left(sorted_nums, nums[1]) + 1)
for x in nums[2:]:
v = bisect_left(sorted_nums, x) + 1
gc1 = len(a) - t1.pre(v) # greaterCount(a, v)
gc2 = len(b) - t2.pre(v) # greaterCount(b, v)
if gc1 > gc2 or gc1 == gc2 and len(a) <= len(b):
a.append(x)
t1.add(v)
else:
b.append(x)
t2.add(v)
return a + b