# # Leetcode 第262场周赛题解

## # Problem A - 至少在两个数组中出现的值 (opens new window)

### # 方法一：模拟

• 时间复杂度$\mathcal{O}(N)$
• 空间复杂度$\mathcal{O}(N)$

class Solution:
def twoOutOfThree(self, nums1: List[int], nums2: List[int], nums3: List[int]) -> List[int]:
s1 = set(nums1)
s2 = set(nums2)
s3 = set(nums3)
return list((s1 & s2) | (s1 & s3) | (s2 & s3))

1
2
3
4
5
6

## # Problem B - 获取单值网格的最小操作数 (opens new window)

### # 方法一：贪心

• 时间复杂度$\mathcal{O}(NM)$
• 空间复杂度$\mathcal{O}(NM)$

class Solution {
public:
int minOperations(vector<vector<int>>& grid, int x) {
int n = grid.size(), m = grid[0].size(), mod = grid[0][0] % x;
vector<int> v;
for (auto &row : grid)
for (int cell : row) {
if (cell % x != mod)
return -1;
v.emplace_back(cell / x);
}
int mid = n * m / 2;
nth_element(v.begin(), v.begin() + mid, v.end());
int ans = 0;
for (int vi : v)
ans += abs(vi - v[mid]);
return ans;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

## # Problem C - 股票价格波动 (opens new window)

### # 方法一：数据结构

• 每个时间戳对应的价格
• 当前的最晚时间戳
• 当前的最低价格
• 当前的最高价格

• 各操作时间复杂度均为$\mathcal{O}(\log N)$
• 空间复杂度$\mathcal{O}(N)$

class StockPrice {
multiset<int> prices;
map<int, int> history;

public:
StockPrice() {}

void update(int timestamp, int price) {
if (history.count(timestamp))
prices.erase(prices.find(history[timestamp]));
history[timestamp] = price;
prices.insert(price);
}

int current() {
return history.rbegin()->second;
}

int maximum() {
return *prices.rbegin();
}

int minimum() {
return *prices.begin();
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

## # Problem D - 将数组分成两个数组并最小化数组和的差 (opens new window)

### # 方法一：Meet in the middle + 动态规划 + 双指针

class Solution {
public:
int minimumDifference(vector<int>& nums) {
for (auto &num : nums)
num *= 2;

int n = nums.size() / 2;
int sum = 0;
for (int num : nums)
sum += num;

vector<unordered_set<int>> left(n + 1), right(n + 1);
left[0].insert(0), right[0].insert(0);
for (int i = 0; i < n; ++i) {
for (int j = i; j >= 0; --j) {
for (int val : left[j])
left[j + 1].insert(val + nums[i]);
}
}

for (int i = n; i < n * 2; ++i) {
for (int j = i - n; j >= 0; --j) {
for (int val : right[j])
right[j + 1].insert(val + nums[i]);
}
}

vector<vector<int>> ls(n + 1), rs(n + 1);
for (int i = 0; i <= n; ++i) {
ls[i] = vector<int>(left[i].begin(), left[i].end());
rs[i] = vector<int>(right[i].begin(), right[i].end());
sort(ls[i].begin(), ls[i].end());
sort(rs[i].begin(), rs[i].end());
}

int target = sum / 2;
int dist = INT_MAX;
for (int i = 0; i <= n; ++i) {
int llen = ls[i].size(), rlen = rs[n - i].size();
int pl = 0, pr = rlen - 1;
while (pl < llen && pr >= 0) {
int curr = ls[i][pl] + rs[n - i][pr];
dist = min(dist, abs(curr - target));
if (curr < target)
pl++;
else
pr--;
}
}

return dist;
}
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53