Ändern Sie das Array, um den Unterschied zu minimieren

Question

Sie erhalten ein Array A von n Werte und einen Wert k. Sie müssen entweder jedes Element in A um k erhöhen oder verringern und müssen es nur einmal für jedes Element tun. Ziel ist es, den Unterschied zwischen dem größten und dem kleinsten Element im resultierenden Array A (nach der Modifikation) zu minimieren und diese Differenz auszugeben.

Zum Beispiel A=[1,7], k=4, müssen wir A als [5,3] ändern, dann ist der Unterschied 2, die die minimale Differenz ist, die wir erreichen können.

Kann mir jemand helfen, diese Frage zu lösen?

Answer 1

Hier ist ein Algorithmus mit einem Auftrag von O(n*log(n)):

public class MinDiff 
{ 
    public static void main(String[] args) 
    { 
     int A[] = {1,7}; 
     int k = 4; 
     System.out.println("Input a:=" + Arrays.toString(A) + ", k:=" + k); 
     find(A, k); 
     System.out.println("Output a´:=" + Arrays.toString(A)); 
    } 

    private static void find(int a[], int k) 
    {  
     Arrays.sort(a); 

     int n = a.length; 
     if (k > a[n - 1] - a[0]) 
     { 
      for (int i = 0; i < n; i++) 
       a[i] += k; 
      return; 
     } 

     a[0] = a[0] + k; 
     a[n - 1] = a[n - 1] - k; 

     int max = Math.max(a[0], a[n - 1]); 
     int min = Math.min(a[0], a[n - 1]); 

     for (int index = 1; index < n - 1; index++) 
     { 
      if (a[index] < min) 
       a[index] += k; 
      else if (a[index] > max) 
       a[index] -= k; 
      else if ((a[index] - min) > (max - a[index])) 
       a[index] -= k; 
      else 
       a[index] += k; 

      max = Math.max(a[index], max); 
      min = Math.min(a[index], min); 
     } 
    } 
} 

Input: a: = [1, 7], k: = 4

Output: a': = [5, 3]

Answer 2

My rekursiven dynamischen Programmierlösung in C++ ist die Zeitkomplexität O (N3) -.

#include <iostream> 
    #include <vector> 
    #include <map> 
    #include <cmath> 
    #include <limits> 

    using namespace std; 

    vector <int> v; 
    map < pair <int, pair <int,int> >, int > mp; 

    int k, n; 

    int solve(int index, int minimum, int maximum) 
    { 
      if(index == n) 
        return maximum - minimum; 
      pair <int, pair <int,int> > p = pair <int, pair <int,int> > (index, pair <int,int> (minimum, maximum)); 
      if(mp.find(p) != mp.end()) 
        return mp[p]; 
      int x = v[index] - k, y = v[index] + k; 
      return mp[p] = min(solve(index + 1, min(x, minimum), max(x, maximum)), solve(index + 1, min(y, minimum), max(y, maximum))); 
    } 

    int main() 
    { 
      int p = std::numeric_limits<int>::max(); 
      int q = std::numeric_limits<int>::min(); 
      cin >> k >> n; 
      int x; 
      for(int i = 0;i < n;i++) 
      { 
        cin >> x; 
        v.push_back(x); 
      } 
      cout << solve(0, p, q) << endl; 
      return 0; 
    } 

Answer 3

Hier ist eine Möglichkeit, darüber nachzudenken (man stelle sich ein sortiertes Array, x 's sind a[i] + k und y' s sind a[i] - k)

x 
    x 
     x 
      x 
y    
    y    x[i](min?) 
     y     x 
      y     x[n-1] 
       y[i](min?)  
          y 
           y 

Wenn Sie y[i] als das Minimum, Ihre Wahl für maximale wählen wäre:

max(y[0], x[i + 1]) 

Und wenn Sie x[i] als Minimum wählen ... oh man nicht kann, da jede a[j] ± k, j > i muss klein sein er in dieser sortierten Anordnung.

Wenn Sie x[n-1] als Minimum wählen, wäre Ihre Wahl für das Maximum das größte aller min(x[j],y[j]) where both x[j] and y[j] are greater than or equal to x[n-1] (or just x[j] if y[j] < x[n-1]).

Wenn Sie y[0] als Minimum wählen, würde Ihre Wahl für maximale max(x[j]), vorausgesetzt, dass alle x[j] größer oder gleich y[0].