使用C ++删除数组的所有元素所需的最小操作数。

2024-05-01 08:55:05 333

问题陈述

给定一个整数数组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

使用C ++删除数组的所有元素所需的最小操作数。

问题陈述

算法

示例

热门推荐

随机推荐