logo

TechCodeview

Spraw, aby wszystkie elementy tablicy były równe przy minimalnym koszcie

Biorąc pod uwagę tablicę rozmiarów N zadaniem jest wyrównanie wartości wszystkich elementów minimalny koszt . Koszt zmiany wartości z x na y wynosi abs(x - y).

Testowanie oprogramowania

Przykłady:  

Wejście: tablica [] = [1 100 101]
Wyjście : 100
Wyjaśnienie: Możemy zmienić wszystkie jego wartości na 100 przy minimalnych kosztach
|1 - 100| + |100 - 100| + |101 - 100| = 100



Wejście : tablica [] = [4 6]
Wyjście : 2
Wyjaśnienie: Możemy zmienić wszystkie jego wartości na 5 przy minimalnych kosztach
|4 - 5| + |5 - 6| = 2

Wejście: tablica [] = [5 5 5 5]
Wyjście:
Wyjaśnienie: Wszystkie wartości są już równe.

[Podejście naiwne] Używanie 2 zagnieżdżonych pętli - czas O(n^2) i przestrzeń O(1)

Pamiętaj, że naszą odpowiedzią może być zawsze jedna z wartości tablicy. Nawet w drugim przykładzie powyżej możemy alternatywnie stworzyć oba jako 4 lub oba jako 6 przy tym samym koszcie.
Pomysł polega na tym, aby rozważyć każdą wartość w tablicy jako potencjalną wartość docelową, a następnie obliczyć całkowity koszt konwersji wszystkich pozostałych elementów na tę wartość docelową. Sprawdzając wszystkie możliwe wartości docelowe, możemy znaleźć tę, która skutkuje minimalnym całkowitym kosztem konwersji.

C++ 
// C++ program to Make all array  // elements equal with minimum cost #include    using namespace std; // Function which finds the minimum  // cost to make array elements equal int minCost(vector<int> &arr) {  int n = arr.size();  int ans = INT_MAX;    // Try each element as the target value  for (int i = 0; i < n; i++) {  int currentCost = 0;    // Calculate cost of making all   // elements equal to arr[i]  for (int j = 0; j < n; j++) {  currentCost += abs(arr[j] - arr[i]);  }    // Update minimum cost if current cost is lower  ans = min(ans currentCost);  }    return ans; } int main() {  vector<int> arr = {1 100 101};  cout << minCost(arr) << endl;    return 0; }
Java 
// Java program to Make all array  // elements equal with minimum cost import java.util.*; class GfG {  // Function which finds the minimum   // cost to make array elements equal  static int minCost(int[] arr) {  int n = arr.length;  int ans = Integer.MAX_VALUE;  // Try each element as the target value  for (int i = 0; i < n; i++) {  int currentCost = 0;  // Calculate cost of making all   // elements equal to arr[i]  for (int j = 0; j < n; j++) {  currentCost += Math.abs(arr[j] - arr[i]);  }  // Update minimum cost if current cost is lower  ans = Math.min(ans currentCost);  }  return ans;  }  public static void main(String[] args) {  int[] arr = {1 100 101};  System.out.println(minCost(arr));  } }
Python 
# Python program to Make all array  # elements equal with minimum cost # Function which finds the minimum  # cost to make array elements equal def minCost(arr): n = len(arr) ans = float('inf') # Try each element as the target value for i in range(n): currentCost = 0 # Calculate cost of making all  # elements equal to arr[i] for j in range(n): currentCost += abs(arr[j] - arr[i]) # Update minimum cost if current cost is lower ans = min(ans currentCost) return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
C# 
// C# program to Make all array  // elements equal with minimum cost using System; class GfG {  // Function which finds the minimum   // cost to make array elements equal  static int minCost(int[] arr) {  int n = arr.Length;  int ans = int.MaxValue;  // Try each element as the target value  for (int i = 0; i < n; i++) {  int currentCost = 0;  // Calculate cost of making all   // elements equal to arr[i]  for (int j = 0; j < n; j++) {  currentCost += Math.Abs(arr[j] - arr[i]);  }  // Update minimum cost if current cost is lower  ans = Math.Min(ans currentCost);  }  return ans;  }  static void Main() {  int[] arr = {1 100 101};  Console.WriteLine(minCost(arr));  } }
JavaScript 
// JavaScript program to Make all array  // elements equal with minimum cost // Function which finds the minimum  // cost to make array elements equal function minCost(arr) {  let n = arr.length;  let ans = Number.MAX_SAFE_INTEGER;  // Try each element as the target value  for (let i = 0; i < n; i++) {  let currentCost = 0;  // Calculate cost of making all   // elements equal to arr[i]  for (let j = 0; j < n; j++) {  currentCost += Math.abs(arr[j] - arr[i]);  }  // Update minimum cost if current cost is lower  ans = Math.min(ans currentCost);  }  return ans; } let arr = [1 100 101]; console.log(minCost(arr));

Wyjście 
100

[Oczekiwane podejście - 1] Korzystanie z wyszukiwania binarnego - czas O(n log (zakres)) i przestrzeń O(1)

Pomysł polega na wykorzystaniu wyszukiwania binarnego do skutecznego znalezienia optymalnej wartości, na którą należy przekonwertować wszystkie elementy tablicy. Ponieważ funkcja kosztu całkowitego tworzy krzywą wypukłą (najpierw malejącą, a następnie rosnącą) w całym zakresie możliwych wartości, możemy użyć wyszukiwania binarnego, aby zlokalizować minimalny punkt tej krzywej, porównując koszt w punkcie środkowym z kosztem w punkcie środkowym minus jeden, który mówi nam, w którym kierunku szukać dalej.

Podejście krok po kroku:

  1. Znajdź wartości minimalne i maksymalne w tablicy, aby ustalić zakres wyszukiwania
  2. Użyj wyszukiwania binarnego pomiędzy wartościami minimalnymi i maksymalnymi, aby zlokalizować optymalną wartość docelową
  3. Dla każdej wartości próbnej oblicz całkowity koszt konwersji wszystkich elementów tablicy na tę wartość
  4. Porównaj koszt w bieżącym punkcie środkowym z kosztem w punkcie środkowym minus jeden, aby określić kierunek wyszukiwania
  5. Kontynuuj zawężanie zakresu wyszukiwania, aż do znalezienia konfiguracji o minimalnym koszcie
C++ 
// C++ program to Make all array  // elements equal with minimum cost #include    using namespace std; // Function to find the cost of changing // array values to mid. int findCost(vector<int> &arr int mid) {  int n = arr.size();  int ans = 0;  for (int i=0; i<n; i++) {  ans += abs(arr[i] - mid);  }  return ans; } // Function which finds the minimum cost  // to make array elements equal. int minCost(vector<int> &arr) {  int n = arr.size();  int mini = INT_MAX maxi = INT_MIN;    // Find the minimum and maximum value.  for (int i=0; i<n; i++) {  mini = min(mini arr[i]);  maxi = max(maxi arr[i]);  }    int s = mini e = maxi;  int ans = INT_MAX;    while (s <= e) {  int mid = s + (e-s)/2;    int cost1 = findCost(arr mid);  int cost2 = findCost(arr mid-1);    if (cost1 < cost2) {  ans = cost1;  s = mid + 1;  }  else {  e = mid - 1;  }  }    return ans; } int main() {  vector<int> arr = {1 100 101};  cout << minCost(arr);    return 0; }
Java 
// Java program to Make all array  // elements equal with minimum cost import java.util.*; class GfG {  // Function to find the cost of changing  // array values to mid.  static int findCost(int[] arr int mid) {  int n = arr.length;  int ans = 0;  for (int i = 0; i < n; i++) {  ans += Math.abs(arr[i] - mid);  }  return ans;  }  // Function which finds the minimum cost   // to make array elements equal.  static int minCost(int[] arr) {  int n = arr.length;  int mini = Integer.MAX_VALUE maxi = Integer.MIN_VALUE;  // Find the minimum and maximum value.  for (int i = 0; i < n; i++) {  mini = Math.min(mini arr[i]);  maxi = Math.max(maxi arr[i]);  }  int s = mini e = maxi;  int ans = Integer.MAX_VALUE;  while (s <= e) {  int mid = s + (e - s) / 2;  int cost1 = findCost(arr mid);  int cost2 = findCost(arr mid - 1);  if (cost1 < cost2) {  ans = cost1;  s = mid + 1;  } else {  e = mid - 1;  }  }  return ans;  }  public static void main(String[] args) {  int[] arr = {1 100 101};  System.out.println(minCost(arr));  } }
Python 
# Python program to Make all array  # elements equal with minimum cost # Function to find the cost of changing # array values to mid. def findCost(arr mid): n = len(arr) ans = 0 for i in range(n): ans += abs(arr[i] - mid) return ans # Function which finds the minimum cost  # to make array elements equal. def minCost(arr): n = len(arr) mini = float('inf') maxi = float('-inf') # Find the minimum and maximum value. for i in range(n): mini = min(mini arr[i]) maxi = max(maxi arr[i]) s = mini e = maxi ans = float('inf') while s <= e: mid = s + (e - s) // 2 cost1 = findCost(arr mid) cost2 = findCost(arr mid - 1) if cost1 < cost2: ans = cost1 s = mid + 1 else: e = mid - 1 return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
C# 
// C# program to Make all array  // elements equal with minimum cost using System; class GfG {  // Function to find the cost of changing  // array values to mid.  static int findCost(int[] arr int mid) {  int n = arr.Length;  int ans = 0;  for (int i = 0; i < n; i++) {  ans += Math.Abs(arr[i] - mid);  }  return ans;  }  // Function which finds the minimum cost   // to make array elements equal.  static int minCost(int[] arr) {  int n = arr.Length;  int mini = int.MaxValue maxi = int.MinValue;  // Find the minimum and maximum value.  for (int i = 0; i < n; i++) {  mini = Math.Min(mini arr[i]);  maxi = Math.Max(maxi arr[i]);  }  int s = mini e = maxi;  int ans = int.MaxValue;  while (s <= e) {  int mid = s + (e - s) / 2;  int cost1 = findCost(arr mid);  int cost2 = findCost(arr mid - 1);  if (cost1 < cost2) {  ans = cost1;  s = mid + 1;  } else {  e = mid - 1;  }  }  return ans;  }  static void Main() {  int[] arr = {1 100 101};  Console.WriteLine(minCost(arr));  } }
JavaScript 
// JavaScript program to Make all array  // elements equal with minimum cost // Function to find the cost of changing // array values to mid. function findCost(arr mid) {  let n = arr.length;  let ans = 0;  for (let i = 0; i < n; i++) {  ans += Math.abs(arr[i] - mid);  }  return ans; } // Function which finds the minimum cost  // to make array elements equal. function minCost(arr) {  let n = arr.length;  let mini = Number.MAX_SAFE_INTEGER maxi = Number.MIN_SAFE_INTEGER;  // Find the minimum and maximum value.  for (let i = 0; i < n; i++) {  mini = Math.min(mini arr[i]);  maxi = Math.max(maxi arr[i]);  }  let s = mini e = maxi;  let ans = Number.MAX_SAFE_INTEGER;  while (s <= e) {  let mid = Math.floor(s + (e - s) / 2);  let cost1 = findCost(arr mid);  let cost2 = findCost(arr mid - 1);  if (cost1 < cost2) {  ans = cost1;  s = mid + 1;  } else {  e = mid - 1;  }  }  return ans; } let arr = [1 100 101]; console.log(minCost(arr));

Wyjście 
100

[Podejście oczekiwane - 2] Korzystanie z sortowania - czas O(n Log n) i przestrzeń O(1)

Chodzi o to, aby znaleźć optymalną wartość, do której powinny zostać wyrównane wszystkie elementy, które muszą być jednym z istniejących elementów tablicy. Sortując najpierw tablicę, a następnie iterując po każdym elemencie jako potencjalną wartość docelową, obliczamy koszt przekształcenia wszystkich pozostałych elementów do tej wartości, efektywnie śledząc sumę elementów po lewej i prawej stronie bieżącej pozycji.

Podejście krok po kroku:

  1. Posortuj tablicę, aby przetwarzać elementy w kolejności rosnącej.
  2. Dla każdego elementu jako potencjalną wartość docelową oblicz dwa koszty: podniesienie mniejszych elementów w górę i większe elementy w dół.
  3. Śledź sumy po lewej i prawej stronie, aby efektywnie obliczać te koszty w stałym czasie na iterację.
    • Podniesienie kosztów mniejszych elementów: (wartość bieżąca × liczba mniejszych elementów) - (suma mniejszych elementów)
    • Obniżenie kosztów większych elementów: (suma większych elementów) - (bieżąca wartość × liczba większych elementów)
  4. Porównaj koszt bieżący z kosztem minimalnym.
C++ 
// C++ program to Make all array  // elements equal with minimum cost #include    using namespace std; // Function which finds the minimum cost  // to make array elements equal. int minCost(vector<int> &arr) {  int n = arr.size();  // Sort the array  sort(arr.begin() arr.end());    // Variable to store sum of elements  // to the right side.  int right = 0;  for (int i=0; i<n; i++) {  right += arr[i];  }    int ans = INT_MAX;  int left = 0;    for (int i=0; i<n; i++) {    // Remove the current element from right sum.  right -= arr[i];    // Find cost of incrementing left side elements  int leftCost = i * arr[i] - left;    // Find cost of decrementing right side elements.  int rightCost = right - (n-1-i) * arr[i];    ans = min(ans leftCost + rightCost);    // Add current value to left sum   left += arr[i];  }    return ans; } int main() {  vector<int> arr = {1 100 101};  cout << minCost(arr);    return 0; }
Java 
// Java program to Make all array  // elements equal with minimum cost import java.util.*; class GfG {  // Function which finds the minimum cost   // to make array elements equal.  static int minCost(int[] arr) {  int n = arr.length;  // Sort the array  Arrays.sort(arr);    // Variable to store sum of elements  // to the right side.  int right = 0;  for (int i = 0; i < n; i++) {  right += arr[i];  }  int ans = Integer.MAX_VALUE;  int left = 0;  for (int i = 0; i < n; i++) {  // Remove the current element from right sum.  right -= arr[i];  // Find cost of incrementing left side elements  int leftCost = i * arr[i] - left;  // Find cost of decrementing right side elements.  int rightCost = right - (n - 1 - i) * arr[i];  ans = Math.min(ans leftCost + rightCost);  // Add current value to left sum   left += arr[i];  }  return ans;  }  public static void main(String[] args) {  int[] arr = {1 100 101};  System.out.println(minCost(arr));  } }
Python 
# Python program to Make all array  # elements equal with minimum cost # Function which finds the minimum cost  # to make array elements equal. def minCost(arr): n = len(arr) # Sort the array arr.sort() # Variable to store sum of elements # to the right side. right = sum(arr) ans = float('inf') left = 0 for i in range(n): # Remove the current element from right sum. right -= arr[i] # Find cost of incrementing left side elements leftCost = i * arr[i] - left # Find cost of decrementing right side elements. rightCost = right - (n - 1 - i) * arr[i] ans = min(ans leftCost + rightCost) # Add current value to left sum  left += arr[i] return ans if __name__ == '__main__': arr = [1 100 101] print(minCost(arr))
C# 
// C# program to Make all array  // elements equal with minimum cost using System; class GfG {  // Function which finds the minimum cost   // to make array elements equal.  static int minCost(int[] arr) {  int n = arr.Length;  // Sort the array  Array.Sort(arr);  // Variable to store sum of elements  // to the right side.  int right = 0;  for (int i = 0; i < n; i++) {  right += arr[i];  }  int ans = int.MaxValue;  int left = 0;  for (int i = 0; i < n; i++) {  // Remove the current element from right sum.  right -= arr[i];  // Find cost of incrementing left side elements  int leftCost = i * arr[i] - left;  // Find cost of decrementing right side elements.  int rightCost = right - (n - 1 - i) * arr[i];  ans = Math.Min(ans leftCost + rightCost);  // Add current value to left sum   left += arr[i];  }  return ans;  }  static void Main() {  int[] arr = {1 100 101};  Console.WriteLine(minCost(arr));  } }
JavaScript 
// JavaScript program to Make all array  // elements equal with minimum cost // Function which finds the minimum cost  // to make array elements equal. function minCost(arr) {  let n = arr.length;  // Sort the array  arr.sort((a b) => a - b);  // Variable to store sum of elements  // to the right side.  let right = 0;  for (let i = 0; i < n; i++) {  right += arr[i];  }  let ans = Number.MAX_SAFE_INTEGER;  let left = 0;  for (let i = 0; i < n; i++) {  // Remove the current element from right sum.  right -= arr[i];  // Find cost of incrementing left side elements  let leftCost = i * arr[i] - left;  // Find cost of decrementing right side elements.  let rightCost = right - (n - 1 - i) * arr[i];  ans = Math.min(ans leftCost + rightCost);  // Add current value to left sum   left += arr[i];  }  return ans; } let arr = [1 100 101]; console.log(minCost(arr));

Wyjście 
100
Utwórz quiz