logo

TechCodeview

Tüm dizi öğelerini minimum maliyetle eşit hale getirin

Bir boyut dizisi verildiğinde N görev, tüm öğelerin değerini eşit hale getirmektir minimum maliyet . Bir değeri x'ten y'ye değiştirmenin maliyeti abs(x - y).

Örnekler:  

linux dizinini yeniden adlandır

Giriş: dizi[] = [1 100 101]
Çıkış : 100
Açıklama: Tüm değerlerini minimum maliyetle 100 olarak değiştirebiliriz
|1 - 100| + |100 - 100| + |101 - 100| = 100



Giriş : dizi[] = [4 6]
Çıkış : 2
Açıklama: Tüm değerlerini minimum maliyetle 5'e çevirebiliriz
|4 - 5| + |5 - 6| = 2

Giriş: dizi[] = [5 5 5 5]
Çıkış:
Açıklama: Zaten tüm değerler eşit.

[Naif Yaklaşım] 2 İç İçe Döngü Kullanma - O(n^2) zaman ve O(1) uzay

Cevabımızın her zaman dizi değerlerinden biri olabileceğini lütfen unutmayın. Yukarıdaki ikinci örnekte bile alternatif olarak ikisini de 4 veya ikisini birden 6 olarak aynı maliyetle yapabiliriz.
Buradaki fikir, dizideki her değeri potansiyel bir hedef değer olarak ele almak ve ardından diğer tüm öğeleri bu hedef değere dönüştürmenin toplam maliyetini hesaplamaktır. Olası tüm hedef değerleri kontrol ederek, minimum toplam dönüşüm maliyetiyle sonuçlanan değeri bulabiliriz.

anlamsal hata
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));

Çıkış 
100

[Beklenen Yaklaşım - 1] İkili Aramayı Kullanma - O(n Log (Range)) zamanı ve O(1) alanı

Buradaki fikir, tüm dizi öğelerinin dönüştürülmesi gereken en uygun değeri verimli bir şekilde bulmak için ikili aramayı kullanmaktır. Toplam maliyet fonksiyonu olası değerler aralığı boyunca dışbükey bir eğri oluşturduğundan (önce azalan sonra artan) bu eğrinin minimum noktasını bulmak için orta noktadaki maliyeti orta nokta eksi bir maliyetle karşılaştırarak, hangi yönde daha fazla arama yapmamız gerektiğini söyleyen ikili aramayı kullanabiliriz.

Adım adım yaklaşım:

  1. Arama aralığını oluşturmak için dizideki minimum ve maksimum değerleri bulun
  2. Optimum hedef değeri bulmak için minimum ve maksimum değerler arasında ikili aramayı kullanın
  3. Her deneme değeri için tüm dizi öğelerini bu değere dönüştürmenin toplam maliyetini hesaplayın
  4. Arama yönünü belirlemek için mevcut orta noktadaki maliyeti orta nokta eksi bir maliyetle karşılaştırın
  5. Minimum maliyet yapılandırmasını bulana kadar arama aralığını daraltmaya devam edin
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));

Çıkış 
100

[Beklenen Yaklaşım - 2] Sıralamanın Kullanılması - O(n Log n) zaman ve O(1) uzay

Buradaki fikir, mevcut dizi elemanlarından biri olması gereken tüm elemanların eşitlenmesi gereken en uygun değeri bulmaktır. Önce diziyi sıralayıp ardından her bir öğeyi potansiyel bir hedef değer olarak yineleyerek, mevcut konumun solundaki ve sağındaki öğelerin toplamını verimli bir şekilde izleyerek diğer tüm öğeleri bu değere dönüştürmenin maliyetini hesaplarız.

Adım adım yaklaşım:

  1. Diziyi, öğeleri artan sırada işleyecek şekilde sıralayın.
  2. Potansiyel hedef değer olarak her bir öğe için iki maliyeti hesaplayın: daha küçük öğeleri yukarı ve daha büyük öğeleri aşağı çekmek.
  3. Bu maliyetleri yineleme başına sabit sürede verimli bir şekilde hesaplamak için sol ve sağ toplamları izleyin.
    • Daha küçük elemanların maliyetini artırmak: (mevcut değer × daha küçük elemanların sayısı) - (daha küçük elemanların toplamı)
    • Daha büyük elemanların maliyetlerini düşürmek: (daha büyük elemanların toplamı) - (mevcut değer × daha büyük elemanların sayısı)
  4. Mevcut maliyeti minimum maliyetle karşılaştırın.
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));

Çıkış 
100
Test Oluştur