Somma di array unica minima

Question

Ho ricevuto una domanda di intervista e il mio algoritmo ha superato solo casi di test esemplificativi e non ha superato tutti i casi di test.

Domanda: Dato un array intero ordinato, restituisce la somma dell'array in modo che ogni elemento sia univoco aggiungendo alcuni numeri per duplicare gli elementi in modo tale che la somma di elementi univoci sia minima.

I.e., se tutti gli elementi dell'array sono univoci, restituire la somma. Se alcuni elementi sono duplicati, incrementali per assicurarti che tutti gli elementi siano univoci in modo che la somma di questi elementi univoci sia minima.

Alcuni esempi:

• input1[] = { 2, 3, 4, 5 } =>return 19 = 2 + 3 + 4 + 5 (tutti gli elementi sono unici, quindi basta sommare)
• input2[] = { 1, 2, 2 } =>return 6 = 1 + 2 +3 (indice 2 è duplicato, così incrementarlo)
• input3[] = { 2, 2, 4, 5 } =>return 14 = 2 + 3 + 4 + 5 (indice 1 è duplicato, così incrementarlo)

Questi tre sono esempi nella domanda, il mio semplice algoritmo è il seguente e ha passato i tre esempi forniti, ma non ha superato altri casi in cui non sono riuscito a vedere gli input.

static int minUniqueSum(int[] A) { 
    int n = A.length; 


    int sum = A[0]; 
    int prev = A[0]; 

    for(int i = 1; i < n; i++) { 
     int curr = A[i]; 

     if(prev == curr) { 
      curr = curr+1; 
      sum += curr; 
     } 
     else { 
      sum += curr; 
     } 
     prev = curr; 
    } 

    return sum; 
} 

non ho potuto vedere gli altri ingressi che questo algoritmo non è riuscita. Quello che mi viene in mente altri esempi di ingresso sono

{1, 1, 1, 1} --> {1, 2, 3, 4} 
{1, 1, 2, 2, 3, 3, 3} --> {1, 2, 3, 4, 5, 6, 7} 

{1, 2, 4, 4, 7, 7, 8} --> I think this should be {1, 2, 3, 4, 6, 7, 8} and my algorithm fails in this example because my algorithm has {1, 2, 4, 5, 7, 8, 9} whose sum is not minimum 

Quali sono alcuni altri casi di test e un algoritmo che può passare tutti i casi?

Alcune persone si lamentano che la domanda non è chiara. Vorrei farti sapere del problema. Non c'era una chiara descrizione del numero aggiunto se sarà permesso solo positivo, positivo o negativo. Dati tre esempi con input e output e altri casi di input e output che non è possibile vedere, scrivere un programma per passare anche tutti gli altri casi di input/output non visti. Questa era la domanda.

Answer 1

l'algoritmo fallirà nei casi con valori più ripetuti, per esempio

2, 2, 2

Otterreste 7 invece di 9.

una correzione minima utilizzando il tuo algoritmo sarebbe:

static int minUniqueSum(int[] A) { 
    int n = A.length; 

    int sum = A[0]; 
    int prev = A[0]; 

    for(int i = 1; i < n; i++) { 
     int curr = A[i]; 

     if(prev >= curr) { 
      curr = prev+1; 
     } 
     sum += curr; 
     prev = curr; 
    } 

    return sum; 
} 

* Come sottolineato nei commenti, no bisogno di ordinare una matrice già ordinata.

Answer 2

È possibile aggiungere valori negativi a qualsiasi input, quindi il minimo è solo il numero triangolare Nth dove N è il numero di elementi nell'array. (Suppongo che si tratti solo di numeri positivi per l'array corretto poiché altrimenti potremmo renderlo arbitrariamente piccolo (negativo)

Quindi l'algoritmo è solo una questione di ricerca di un paio di numeri consecutivi valori ugualiSe non trovato, restituire la somma N * (N + 1)/2.

---

Se invece è vero che solo duplicato elementi può essere regolato, allora l'approccio è quello di trovare buchi tra elementi consecutivi e riempirli con precedenza "in coda" valori. I valori effettivi degli elementi "in coda" sono irrilevanti e solo un contatore è necessario. Di seguito è riportata una soluzione C# in cui presumo che gli aggiustamenti agli elementi debbano essere valori positivi. Ciò significa che non possiamo andare indietro e riempire buchi inutilizzati che semplificano il problema.

int F() 
{ 
    int[] a = {2, 2, 2, 3, 8, 9}; // sorted list 

    int n = 0; /* num */ int p = 0; /* prev; zero is an invalid value in the list */ 
    int q = 0; /* queue */ int s = 0; /* sum */ 

    for (int i = 1; i < a.Length; i++) 
    { 
     n = a[i]; 
     if (n == p) 
      q++; // increment queue on duplicate number 
     else 
     { 
      // for every hole between array values, decrement queue and add to the sum 
      for (int j = 1; q > 0 && j < n - p; j++, q--) 
       s += p + j; 
      s += (p = n); 
     } 
    } 
    // flush the queue 
    for (; q > 0; q--) 
     s += ++n; 

    return s; 
} 

---

Si esempio {1, 2, 4, 4, 7, 7, 8} suggerisce che l'ipotesi precedente non è valido. Così sono andato avanti e ho scritto una versione che utilizza una coda per memorizzare i buchi saltati per il riempimento successivo. Non è poi così doloroso, ed è molto simile nella struttura, ma potrebbe essere ancora troppo per la maggior parte delle interviste.

using System.Collections.Generic; 
int F2() 
{ 
    int[] a = {1, 1, 8, 8, 8, 8, 8}; // sorted list 

    int n = 0; /* num */ int p = 0; // prev; zero is an invalid value in the list 
    int q = 0; /* queue */ int s = 0; // sum 
    Queue<int> h = new Queue<int>(); // holes 

    for (int i = 1; i < a.Length; i++) 
    { 
     n = a[i]; 
     if (n == p) 
      q++; // increment queue on duplicate number 
     else 
     { 
      for (int j = 1; j < n - p; j++) 
       if (h.Count <= q + a.Length - i) // optimization 
        h.Enqueue(p + j); 
      s += (p = n); 
     } 
    } 
    // flush the queue 
    for (; q > 0; q--) 
     s += h.Count > 0 ? h.Dequeue() : ++n; 

    return s; 
} 

entrambi provare qui: http://rextester.com/APO79723

Answer 3

int a[] = {1,2,2,3,5,6,6,6,6 }; So what would be elements in array for sum 
As per above problem statement it would be {1,2,3,4,5,6,7,8,9 } 

Solution 
public static void uniqueSum(){ 
     int a[] = {1,2,2,3,5,6,6,6,6 }; 
     int n = a.length; 
     int sum = a[0]; 
     int prv=a[0]; 
     for(int i=1; i<n;i++){ 
      int cur = a[i]; 
      if(cur==prv){ 
       cur = cur+1; 
       sum+= cur; 
       System.out.print("--"+cur); 
      }else{ 
       if(cur<prv){ 
        cur = prv +1; 
       } 
       sum += cur; 
      } 
      prv = cur; 
     } 
     System.out.println("===================== "+sum); 
    } 

Answer 4

si può provare il codice qui sotto.

int a[] = {1, 1 , 1}; 
ArrayList<Integer> arr = new ArrayList<Integer>(); 
HashMap hash = new HashMap(); 
for(int i=0;i<a.length;i++){ 
    arr.add(a[i]); 
} 
int sum = 0; 
hash.put(0, arr.get(0)); 
sum = (int) hash.get(0); 
for(int i=1;i<arr.size();i++){ 
    for(int j=1;j<=a.length;j++){ 
     if(hash.containsValue((arr.get(i)))){ 
      arr.set(i, arr.get(i)+1); 
     }else{ 
      hash.put(i, arr.get(i)); 
      sum += (int) hash.get(i); 
      break; 
     } 
    } 
} 

System.out.println(sum); 

PS: Anche io ho avuto questa domanda nella mia intervista, il codice di cui sopra ha superato tutti i casi di test.

Answer 5

public static int minSum (int arr []) {

for(int i=0; i<arr.length-1;i++){ 

     if(arr[i]==arr[i+1]){ 

      arr[i+1]= arr[i+1]+1; 
     } 
    } 

    int sum=0; 

    for(int i=0; i<arr.length;i++){ 

     sum=sum+arr[i]; 
    } 

    System.out.println("sum: "+sum); 
    return sum; 
}