資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中將陣列大小減半
假設我們有一個數組 arr。我們可以選擇一組整數並刪除陣列中這些整數的所有出現。我們必須找到集合的最小大小，以便刪除陣列中至少一半的整數。例如，如果 arr = [3,3,3,3,5,5,5,2,2,7]，則輸出將為 2。這是因為如果我們選擇 {3,7}，這將使新陣列 [5,5,5,2,2]，其大小為 5（這等於舊陣列大小的一半）。大小為 2 的可能集合為 {3,5}、{3,2}、{5,2}。選擇集合 {2,7} 是不可能的，因為它將使新陣列 [3,3,3,3,5,5,5]，其大小大於舊陣列大小的一半。
為了解決這個問題，我們將遵循以下步驟：
定義一個對映 m，n := arr 的大小，將 arr 中存在的每個元素的頻率儲存到對映 m 中
定義一個名為 temp 的陣列，sz := n，以及 ret := 0
對於 m 中的每個鍵值對 it
將 it 的值插入到 temp 中
對 temp 陣列進行排序
對於 I 從 0 到 temp 的大小
如果 sz <= n / 2，則退出迴圈
將 ret 加 1
將 sz 減去 temp[i]
返回 ret
示例 (C++)
讓我們看看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minSetSize(vector<int>& arr) {
unordered_map <int, int> m;
int n = arr.size();
for(int i = 0; i < n; i++){
m[arr[i]]++;
}
vector <int> temp;
unordered_map <int, int> :: iterator it = m.begin();
int sz = n;
int ret = 0;
while(it != m.end()){
temp.push_back(it->second);
it++;
}
sort(temp.rbegin(), temp.rend());
for(int i = 0; i < temp.size(); i++){
if(sz <= n / 2)break;
ret++;
sz -= temp[i];
}
return ret;
}
};
main(){
vector<int> v = {3,3,3,3,5,5,5,2,2,7};
Solution ob;
cout << (ob.minSetSize(v));
}輸入
[3,3,3,3,5,5,5,2,2,7]
輸出
2
更新於: 2020-04-29
1K+ 瀏覽量
廣告