Skip to content

Commit 307293d

Browse files
gazeldxgazeldx
committed
Added 3478-choose-k-elements-with-maximum-sum.md with Python solution.
1 parent cd5daa6 commit 307293d

File tree

2 files changed

+262
-0
lines changed

2 files changed

+262
-0
lines changed

‎en/3001-4000/3478-choose-k-elements-with-maximum-sum.md

Lines changed: 130 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,130 @@
1+
Original link: [coding5.com - Best practices of LeetCode solutions](https://coding5.com/en/leetcode/3478-choose-k-elements-with-maximum-sum)
2+
3+
# 3478. Choose K Elements With Maximum Sum - Best practices of LeetCode solutions
4+
5+
LeetCode link: [3478. Choose K Elements With Maximum Sum](https://leetcode.com/problems/choose-k-elements-with-maximum-sum), Difficulty: **Medium**.
6+
7+
## LeetCode description of "3478. Choose K Elements With Maximum Sum"
8+
9+
You are given two integer arrays, `nums1` and `nums2`, both of length `n`, along with a positive integer `k`.
10+
11+
For each index `i` from `0` to `n - 1`, perform the following:
12+
13+
- Find all indices `j` where `nums1[j]` is less than `nums1[i]`.
14+
- Choose at most `k` values of `nums2[j]` at these indices to maximize the total sum.
15+
16+
Return an array `answer` of size `n`, where `answer[i]` represents the result for the corresponding index `i`.
17+
18+
### [Example 1]
19+
20+
**Input**: `nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2`
21+
22+
**Output**: `[80,30,0,80,50]`
23+
24+
**Explanation**:
25+
26+
```
27+
- For `i = 0`: Select the 2 largest values from `nums2` at indices `[1, 2, 4]` where `nums1[j] < nums1[0]`, resulting in `50 + 30 = 80`.
28+
- For `i = 1`: Select the 2 largest values from `nums2` at index `[2]` where `nums1[j] < nums1[1]`, resulting in `30`.
29+
- For `i = 2`: No indices satisfy `nums1[j] < nums1[2]`, resulting in `0`.
30+
- For `i = 3`: Select the 2 largest values from `nums2` at indices `[0, 1, 2, 4]` where `nums1[j] < nums1[3]`, resulting in `50 + 30 = 80`.
31+
- For `i = 4`: Select the 2 largest values from `nums2` at indices `[1, 2]` where `nums1[j] < nums1[4]`, resulting in `30 + 20 = 50`.
32+
```
33+
34+
### [Example 2]
35+
36+
**Input**: `nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1`
37+
38+
**Output**: `[0,0,0,0]`
39+
40+
**Explanation**:
41+
42+
```
43+
Since all elements in `nums1` are equal, no indices satisfy the condition `nums1[j] < nums1[i]` for any `i`, resulting in `0` for all positions.
44+
```
45+
46+
### [Constraints]
47+
48+
- `n == nums1.length == nums2.length`
49+
- `1 <= n <= 10^5`
50+
- `1 <= nums1[i], nums2[i] <= 10^6`
51+
- `1 <= k <= n`
52+
53+
### [Hints]
54+
55+
<details>
56+
<summary>Hint 1</summary>
57+
Sort `nums1` and its corresponding `nums2` values together based on `nums1`.
58+
59+
60+
</details>
61+
62+
<details>
63+
<summary>Hint 2</summary>
64+
Use a max heap to track the top `k` values of `nums2` as you process each element in the sorted order.
65+
66+
67+
</details>
68+
69+
## Intuition
70+
71+
* Seeing this, everyone will definitely think of sorting `nums1` from small to large, so that the front is less than or equal to the back, but the indexes will be **messy** when sorting. If there is no good way to solve this problem, the whole question cannot be solved. Please think about it first.
72+
73+
ddd Bring the `index` when sorting, that is, the object to be sorted is an array of tuples of `(num, index)`. This technique **must be mastered**, as it will be used in many questions.ddd
74+
75+
After solving the above problems, the indexes are all there, let's continue reading:
76+
77+
* Requirement 2: Choose at most `k` values of `nums2[j]` at these indices to **maximize** the total sum.
78+
79+
After seeing this, have you thought of any good method?
80+
81+
ddd Heap sort, maintain a large root heap of size `k`. This is also a knowledge point that is often tested, **must be mastered**. ddd
82+
83+
Seeing this, please implement the code according to the above prompts.
84+
85+
* Finally, it is found that the repeated `num` that appear continuously should be specially processed, that is, the values ​​in `answer` corresponding to the same `num` should be the same. There are many ways to deal with it. What is the simplest way to deal with it?
86+
87+
ddd Use a `Map`, `key` is `num`, and the same `key` directly uses the `value` corresponding to `key`. ddd
88+
89+
## Complexity
90+
91+
- Time complexity: `O(N * logN)`.
92+
- Space complexity: `O(N)`.
93+
94+
## Python
95+
96+
```python
97+
class Solution:
98+
def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
99+
num_index_list = [(num, index) for index, num in enumerate(nums1)] # key 1
100+
num_index_list.sort()
101+
102+
answer = [None] * len(nums1)
103+
k_max_nums = []
104+
sum_ = 0
105+
num_to_sum = defaultdict(int) # key 2
106+
107+
for i, num_index in enumerate(num_index_list):
108+
num, index = num_index
109+
110+
if num in num_to_sum:
111+
answer[index] = num_to_sum[num]
112+
else:
113+
answer[index] = sum_
114+
num_to_sum[num] = sum_
115+
116+
heapq.heappush(k_max_nums, nums2[index])
117+
sum_ += nums2[index]
118+
119+
if len(k_max_nums) > k:
120+
num = heapq.heappop(k_max_nums) # key 3
121+
sum_ -= num
122+
123+
return answer
124+
```
125+
126+
## Other languages
127+
128+
```java
129+
// Welcome to create a PR to complete the code of this language, thanks!
130+
```

‎zh/3001-4000/3478-choose-k-elements-with-maximum-sum.md

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
原文链接：[coding5.com - 力扣题解最佳实践](https://coding5.com/zh/leetcode/3478-choose-k-elements-with-maximum-sum)
2+
3+
# 3478. 选出和最大的 K 个元素 - 力扣题解最佳实践
4+
5+
力扣链接：[3478. 选出和最大的 K 个元素](https://leetcode.cn/problems/choose-k-elements-with-maximum-sum), 难度：**中等**。
6+
7+
## 力扣“3478. 选出和最大的 K 个元素”问题描述
8+
9+
给你两个整数数组，`nums1` 和 `nums2`，长度均为 `n`，以及一个正整数 `k` 。
10+
11+
对从 `0` 到 `n - 1` 每个下标 `i` ，执行下述操作：
12+
13+
- 找出所有满足 `nums1[j]` 小于 `nums1[i]` 的下标 `j` 。
14+
- 从这些下标对应的 `nums2[j]` 中选出 至多 `k` 个，并 最大化 这些值的总和作为结果。
15+
16+
返回一个长度为 `n` 的数组 `answer` ，其中 `answer[i]` 表示对应下标 `i` 的结果。
17+
18+
19+
### [示例 1]
20+
21+
**输入**: `nums1 = [4,2,1,5,3], nums2 = [10,20,30,40,50], k = 2`
22+
23+
**输出**: `[80,30,0,80,50]`
24+
25+
**解释**:
26+
27+
```
28+
- 对于 `i = 0` ：满足 `nums1[j] < nums1[0]` 的下标为 `[1, 2, 4]` ，选出其中值最大的两个，结果为 `50 + 30 = 80` 。
29+
- 对于 `i = 1` ：满足 `nums1[j] < nums1[1]` 的下标为 `[2]` ，只能选择这个值，结果为 `30` 。
30+
- 对于 `i = 2` ：不存在满足 `nums1[j] < nums1[2]` 的下标，结果为 `0` 。
31+
- 对于 `i = 3` ：满足 `nums1[j] < nums1[3]` 的下标为 `[0, 1, 2, 4]` ，选出其中值最大的两个，结果为 `50 + 30 = 80` 。
32+
- 对于 `i = 4` ：满足 `nums1[j] < nums1[4]` 的下标为 `[1, 2]` ，选出其中值最大的两个，结果为 `30 + 20 = 50` 。
33+
```
34+
35+
### [示例 2]
36+
37+
**输入**: `nums1 = [2,2,2,2], nums2 = [3,1,2,3], k = 1`
38+
39+
**输出**: `[0,0,0,0]`
40+
41+
**解释**:
42+
43+
```
44+
由于 `nums1` 中的所有元素相等，不存在满足条件 `nums1[j] < nums1[i]`，所有位置的结果都是 `0` 。
45+
```
46+
47+
### [约束]
48+
49+
- `n == nums1.length == nums2.length`
50+
- `1 <= n <= 10^5`
51+
- `1 <= nums1[i], nums2[i] <= 10^6`
52+
- `1 <= k <= n`
53+
54+
### [Hints]
55+
56+
<details>
57+
<summary>提示 1</summary>
58+
Sort `nums1` and its corresponding `nums2` values together based on `nums1`.
59+
60+
61+
</details>
62+
63+
<details>
64+
<summary>提示 2</summary>
65+
Use a max heap to track the top `k` values of `nums2` as you process each element in the sorted order.
66+
67+
68+
</details>
69+
70+
## 思路
71+
72+
- 要求1：找出所有满足 `nums1[j]` 小于 `nums1[i]` 的下标 `j` 。
73+
看到这个，大家一定会想到把 `nums1` 按从小到大排序，这样，前面的小于等于后面的，但一排序下标就**乱**了。如果对这个问题没有好办法解决，整个题目就做不出来。先请思考下。
74+
75+
ddd在排序时带上索引下标，即排序的对象是元组`(num, index)`的数组。这个技术**一定要掌握**，许多题目都会用到。ddd
76+
77+
解决了上面的问题，下标就都有了，我们再看：
78+
79+
- 要求2：从这些下标对应的 `nums2[j]` 中选出 至多 `k` 个，并 **最大化** 这些值的总和作为结果。
80+
81+
看到这个，你想到用什么好方法了吗？
82+
83+
ddd堆排序，维护一个大小为 `k` 的大根堆。这也是经常考察的知识点，**一定要掌握**哦。ddd
84+
85+
看到这，请你先按上文提示把代码实现一下。
86+
87+
- 最后，发现还要对连续出现的重复的 `num` 进行特别处理，即相同的 `num` 对应的 `answer` 中的值应该是一样的。处理方法有多种，怎么处理最简单呢？
88+
89+
ddd 用一个 `Map`， `key`为 `num`, 相同的 `key` 直接使用 `key` 对应的`值`。ddd
90+
91+
## 复杂度
92+
93+
- 时间复杂度: `O(N * logN)`.
94+
- 空间复杂度: `O(N)`.
95+
96+
## Python
97+
98+
```python
99+
class Solution:
100+
def findMaxSum(self, nums1: List[int], nums2: List[int], k: int) -> List[int]:
101+
num_index_list = [(num, index) for index, num in enumerate(nums1)] # key 1
102+
num_index_list.sort()
103+
104+
answer = [None] * len(nums1)
105+
k_max_nums = []
106+
sum_ = 0
107+
num_to_sum = defaultdict(int) # key 2
108+
109+
for i, num_index in enumerate(num_index_list):
110+
num, index = num_index
111+
112+
if num in num_to_sum:
113+
answer[index] = num_to_sum[num]
114+
else:
115+
answer[index] = sum_
116+
num_to_sum[num] = sum_
117+
118+
heapq.heappush(k_max_nums, nums2[index])
119+
sum_ += nums2[index]
120+
121+
if len(k_max_nums) > k:
122+
num = heapq.heappop(k_max_nums) # key 3
123+
sum_ -= num
124+
125+
return answer
126+
```
127+
128+
## Other languages
129+
130+
```java
131+
// Welcome to create a PR to complete the code of this language, thanks!
132+
```

0 commit comments

Comments
 (0)