C++ 中使所有数组元素相等所需的最少运算次数
c++server side programmingprogramming
问题描述
给定一个包含 n 个正整数的数组。我们需要找到使所有元素相等的最少运算次数。我们可以对数组元素上的任意元素执行加法、乘法、减法或除法。
示例
如果输入数组为 {1, 2, 3, 4}，则至少需要 3 次运算才能使所有元素相等。例如，我们可以通过执行 3 次加法使元素相等。
算法
1. 选择出现频率最高的元素。我们称之为"x" 2. 现在我们需要执行 n-x 次运算，因为有 x 个元素具有相同的值
示例
#include <bits/stdc++.h>
using namespace std;
int getMinOperations(int *arr, int n) {
unordered_map<int, int> hash;
for (int i = 0;i < n; ++i) {
hash[arr[i]]++;
}
int maxFrequency = 0;
for (auto elem : hash) {
if (elem.second > maxFrequency) {
maxFrequency = elem.second;
}
}
return (n - maxFrequency);
}
int main() {
int arr[] = {1, 2, 3, 4};
int n = sizeof(arr) / sizeof(arr[0]);
cout << "最低要求操作 = " <<
getMinOperations(arr, n) << endl;
return 0;
}
编译并执行上述程序，将生成以下输出:
输出
最低要求操作 = 3
