使用 C/C++ 進行陣列操作和求和

這裡我們將瞭解一個問題，假設給定一個陣列。有 n 個元素。還給出一個值 S。我們必須在陣列中找到一個元素 K，使得如果將所有大於 K 的元素都改成 K，則最終陣列的所有元素的總和將變成 S。如果不可能，則返回 -1。

假設元素為 {12, 6, 3, 7, 8}，求和值為 15，輸出為 3。最終陣列為 {3, 3, 3, 3, 3}，陣列元素的總和為 S = 15

演算法

getVal(arr, n, S) −

Begin
   sort arr as increasing order
   sum := 0
   for i in range 0 to n-1, do
      if sum + (arr[i] * (n - i)) is same as S, then
         return arr[i]
      end if
      sum := sum + arr[i]
   done
   return -1
End

示例

#include <iostream>
#include <algorithm>
using namespace std;
int getVal(int arr[], int n, int S) {
   sort(arr, arr + n);
   int sum = 0;
   for (int i = 0; i < n; i++) {
      if (sum + (arr[i] * (n - i)) == S) //if current value is satisfying, then return arr[i]
         return arr[i];
      sum += arr[i];
   }
   return -1;
}
int main() {
   int S = 15;
   int arr[] = { 12, 3, 6, 7, 8 };
   int n = sizeof(arr) / sizeof(arr[0]);
   cout << getVal(arr, n, S);
}

輸出

3

更新於：20-Aug-2019

2K+ 瀏覽量

開啟您的 職業生涯

完成課程認證

開始
廣告