資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究使用 C++ 刪除陣列中所有元素所需的最小操作次數。
問題陳述
給定一個整數陣列 arr，任務是列印刪除陣列中所有元素所需的最小操作次數。在刪除元素時，施加以下限制：
可以隨機選擇陣列中的任何元素，並且可以刪除陣列中所有能被其整除的元素。
如果 arr[] = {2, 4, 15, 10, 8, 5, 3}，則需要 3 次操作才能刪除所有元素：
- 如果我們選擇 2，它將刪除 {2, 4, 10, 8}
- 如果我們選擇 5，它將刪除 {5, 15}
- 如果我們選擇 3，它將刪除 {3}
演算法
1. Sort the array in ascending order and count number occurrence of each element 2. For each unmarked element starting from beginning mark all elements which are divisible by choose element, and increase the result counter
示例
#include <iostream>
#include <algorithm>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define MAX 100
using namespace std;
int getMinOperations(int *arr, int n){
int map[MAX] = {0};
sort(arr, arr + n);
for (int i = 0; i < n; ++i) {
map[arr[i]]++;
}
int cnt = 0;
for (int i = 0; i < n; ++i) {
if (map[arr[i]]) {
for (int j = i; j < n; ++j) {
if (arr[j] % arr[i] == 0) {
map[arr[j]] = 0;
}
}
++cnt;
}
}
return cnt;
}
int main(){
int arr[] = {2, 4, 15, 10, 8, 5, 3};
cout << "Minimum required operations = " << getMinOperations(arr, SIZE(arr)) << endl;
return 0;
}輸出
編譯並執行上述程式時，它會生成以下輸出：
Minimum required operations = 3
更新於: 2019年10月31日
1K+ 瀏覽量
廣告