数据结构
网络
关系数据库管理系统
操作系统
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+ 浏览量
广告