資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 使陣列變為“好陣列”所需移除的最小元素數。
問題陳述
給定一個數組“arr”，任務是找到使陣列變為“好陣列”所需移除的最小元素數。
如果對於每個元素 a[i]，都存在一個元素 a[j]（i 不等於 j），使得 a[i] + a[j] 是 2 的冪，則序列 a1、a2、a3…an 被稱為“好陣列”。
arr1[] = {1, 1, 7, 1, 5}在上面的陣列中，如果我們刪除元素 '5'，則陣列變為“好陣列”。在此之後，arr[i] + arr[j] 的任意一對都是 2 的冪 -
- arr[0] + arr[1] = (1 + 1) = 2，它是 2 的冪
- arr[0] + arr[2] = (1 + 7) = 8，它是 2 的冪
演算法
1. We have to delete only such a[i] for which there is no a[j] such that a[i] + a[i] is a power of 2. 2. For each value find the number of its occurrences in the array 3. Check that a[i] doesn’t have a pair a[j]
示例
#include <iostream>
#include <map>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minDeleteRequred(int *arr, int n){
map<int, int> frequency;
for (int i = 0; i < n; ++i) {
frequency[arr[i]]++;
}
int delCnt = 0;
for (int i = 0; i < n; ++i) {
bool doNotRemove = false;
for (int j = 0; j < 31; ++j) {
int pair = (1 << j) - arr[i];
if (frequency.count(pair) &&
(frequency[pair] > 1 ||
(frequency[pair] == 1 &&
pair != arr[i]))) {
doNotRemove = true;
break;
}
}
if (!doNotRemove) {
++delCnt;
}
}
return delCnt;
}
int main(){
int arr[] = {1, 1, 7, 1, 5};
cout << "Minimum elements to be deleted = " << minDeleteRequred(arr, SIZE(arr)) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出 -
Minimum elements to be deleted = 1
更新於: 2019-10-31
891 次檢視
廣告