C++ 通过选择满足 arr[i] >= arr[j] 的配对元素，将数组的最后剩下的元素最小化，并用 arr[i] – arr[j] 替换 arr[i]

给定一个非负整数数组，我们可以对给定数组进行任意次数的操作，以便我们可以选择数组中的任意一个元素，并选择另一个小于或等于当前元素的元素，并将其从第一个元素中减去。如果减去后第一个元素变为零，则将其删除。

在应用上述描述的方法任意次数后，我们需要找到数组中可能的最小元素。

示例示例

输入

int arr[] = {12, 18, 6, 9, 15}

输出

3

解释

我们可以从15中移除6，然后数组会变为：{12，18，6，9，9}。

我们可以从9中移除9，并从数组中移除零：

{12，18，6，9}

我们可以从18中三次删除6，并从12中两次删除，我们将得到{6，9}

最后，我们可以从9中删除6 => {6，3}。

最后，从6中删除两次3，我们将得到3作为最小的最终答案。

输入

int arr[] = {2, 8, 4, 1}

输出

1

Explanation : 我们可以从每个给定的数组元素中最多减去它们自己的次数，得到1作为最小答案。

Observation

我们可以始终从最大的元素中减去最小的元素，所以我们始终可以通过减去最小的元素来减小较大的元素。但是，从较大的元素中减去值后可能会变得更小，然后我们可以用它来减少先前较小的元素，直到其中一个变为零。

因此，对于两个元素x和y，上述方法可以实现如下代码：

伪代码

while(x != 0 || y != 0){
    if(x > y){
        swap(x,y);
}
y = y -x; 
}

这里的事实是，最后剩下的元素将是x和y的最大公约数，因为上面的伪代码对于最大公约数是相同的。

此外，上面代码的时间复杂度是O(min(X,Y))，非常高，相反，我们可以使用C++编程语言的内置最大公约数函数来在对数时间内获得解决方案。

伪代码

while(x != 0 || y !=0 ){
    if(x > y){
        swap(x,y);
}
y = y % x;
}

在上述的方法中，我们使用取模而不是减法，在非常短的时间内得到相同的结果。

方法

我们已经了解了GCD的基础知识，所以在这种方法中，我们将使用内置的gcd函数。让我们看看代码实现的步骤：

• 首先，我们将创建一个函数，并将给定的数组和其大小作为参数传递给该函数，它将返回最终答案作为返回值。

• 在函数中，我们将创建一个整数来存储完整数组的gcd。同时，它将被初始化为0，因为它不会影响数组的gcd。

• 我们将使用for循环遍历数组，在每次迭代中，我们将对当前索引元素和变量的gcd进行计算。

• 我们将使用C ++编程语言的内置gcd函数，并将结果存储在同一变量中。

• 最后，我们将返回最终答案并在主函数中打印它。

示例

#include <bits/stdc++.h>
using namespace std;

// helper function to get the answer 
int getMin(int arr[], int n){
   int gcd = 0; // variable to store the gcd
   // traversing over the given array 
   for(int i=0; i<n; i++){
      gcd = __gcd(gcd, arr[i]);
   }
   // return the final answer
   return gcd;
}
// main function 
int main(){
   int arr[] = {12, 18, 6, 9, 15}; // given array 
   int n = 5; // size of the given array 
   //calling the function 
   int ans = getMin(arr, n);
   cout<<"The minimum element remains in the array after performing the given operations a maximum possible number of times is: "<<ans<<endl;
   return 0;
}

输出

The minimum element remains in the array after performing the given operations a maximum possible number of times is: 3

时间和空间复杂度

上面代码的时间复杂度是O(N*log(max(arr元素))), 这里我们遍历了数组，所以有因素N，而由于有内置的gcd函数，我们得到了log的因素。

上面代码的空间复杂度是O(1), 因为我们没有使用任何额外的空间。

结论

在本教程中，我们实现了一个程序，通过删除其他元素，找到数组中最小的数。如果其他数大于或等于该数，我们可以从其他数中删除该数，如果它变为零，我们将从数组中删除它。我们使用了gcd方法来计算答案，时间复杂度为O(N*log(max_array_element))，空间复杂度为常量。