数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学C++程序：移除子列表以使k值上下元素数量相同
假设我们有一个名为nums的数字列表和另一个数字k，我们可以最多从列表中移除一个子列表。我们必须找到最长结果列表的长度，使得严格小于k的数字和严格大于k的数字的数量相同。
因此，如果输入类似于nums = [6, 10, 8, 9, 3, 5]，k = 6，则输出将为5，因为如果我们移除子列表[9]，我们将得到[6, 10, 8, 3, 5]，并且有两个数字[3, 5]小于6，有两个数字[10, 8]大于6。
为了解决这个问题，我们将遵循以下步骤：
- 定义一个与nums大小相同的数组v，并用0填充。
- cnt := 0
- for i := 0 to nums.size() -1:
- 如果nums[i] < k，则
- cnt += 1
- 否则，如果nums[i] > k，则
- cnt -= 1
- v[i + 1] = cnt
- 如果nums[i] < k，则
- 如果v的最后一个元素为0，则返回nums的大小。
- delta := v的最后一个元素
- 定义一个map m
- ans := 无穷大
- for i := 1 to v.size():
- 如果m[v[i] - v的最后一个元素] != 0 或 (v[i] - v的最后一个元素 == 0)，则：
- ans := min(ans, i - m[v[i] - v的最后一个元素])
- m[v[i]] := i
- 如果m[v[i] - v的最后一个元素] != 0 或 (v[i] - v的最后一个元素 == 0)，则：
- 如果ans == 无穷大，则：
- 返回0
- 否则
- 返回nums的大小
让我们来看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(vector<int>& nums, int k) {
vector<int> v(nums.size() + 1, 0);
int cnt = 0;
for (int i = 0; i < nums.size(); ++i) {
if (nums[i] < k)
++cnt;
else if (nums[i] > k)
--cnt;
v[i + 1] = cnt;
}
if (v.back() == 0) return int(nums.size());
int delta = v.back();
map<int, int> m;
int ans = INT_MAX;
for (int i = 1; i <= v.size(); ++i) {
if (m[v[i] - v.back()] != 0 || v[i] - v.back() == 0) {
ans = min(ans, i - m[v[i] - v.back()]);
}
m[v[i]] = i;
}
if (ans == INT_MAX)
return 0;
else
return int(nums.size() - ans);
}
};
main(){
Solution ob;
vector<int> v = {6, 10, 8, 9, 3, 5};
int k = 6;
cout << ob.solve(v, k); }输入
{6, 10, 8, 9, 3, 5}, 6输出
5
更新于：2020年10月20日
112 次浏览
广告