資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告