Inversioni di conteggio (numero con input grande)

Question

Attualmente sto lavorando all'esercizio del conteggio delle inversioni usando mergesort. Il problema che sto affrontando è quando ho array di piccole o medie dimensioni, il risultato è perfettamente soddisfacente, tuttavia se utilizzo un testcase molto grande (una matrice di 100.000 interi) non mi dà il numero corretto di inversioni. Non ho idea di come mai sta succedendo. Qui è il mio codice:

static int [] helper; 
static long count=0; 
static Integer [] arr3; 

private static void mergeSortMethod(Integer[] arr3) { 
    int head=0; 
    int tail=arr3.length-1; 
    int mid=tail+((head-tail)/2); 

    sort(arr3,head,tail); 
} 


private static void sort(Integer[] arr3, int low, int high) { 

    if (high<=low){ 
     return; 
    } 
    int mid=low+ ((high-low)/2); 

    sort(arr3,low,mid); 
    sort(arr3,mid+1,high); 

    merge3CountInvs(arr3,low,mid,high); 

} 

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) { 
    int i=low; 
    int j=mid+1; 
    int k=low; 
    //to get size of first half of array 
    int nArr1Elems=(mid-low)+1; 

    for (int m=low;m<=high;m++){ 
     helper[m]=arr3[m]; 

    } 

    while(i < mid+1 && j < high+1){// neither array empty 
     if(helper[i] < helper[j]){ 
      arr3[k++] = helper[i++]; 

     } 

     else if (helper[j] < helper[i]){ 
      arr3[k++] = helper[j++]; 
      int numOFElements=nArr1Elems-i; 
      count=count+(nArr1Elems-i); 

     } 
    } 
    while(i < mid+1){ // arrayB is empty, 
     arr3[k++] = helper[i++]; 
    } 

    while(j < high+1){ // arrayA is empty, 
     arr3[k++] = helper[j++]; 
    } 

} 

La mia soluzione dà risposte corrette quando non si utilizza molto grandi ingressi tuttavia quando ho usato banco di prova di 100.000 interi che era il numero di inversioni che ho ricevuto:

Dalla mia realizzazione: - 30588581433

risposta corretta è: 2407905288

Tutte le idee? Gradirei qualsiasi tipo di aiuto. Grazie.

MODIFICA: Come menzionato nelle risposte sul caso di overflow intero è il punto in cui sto avendo difficoltà a capire poiché il "conteggio" delle variabili che causa l'overflow è inizializzato come "lungo", quindi non ci dovrebbero essere overflow in questo caso. Non riesco a pensare a nessuna altra variabile che possa causare un overflow di numeri interi nel mio codice. Molte grazie.

UPDATE:

Non c'era alcun problema relativo alla integer overflow, ma grazie per le risposte però la risposta di Reddy mi ha punto nella giusta direzione quindi grazie ancora una volta. L'unico errore nel mio algoritmo è stato:

int nArr1Elems=(mid-low)+1; 

count=count+(nArr1Elems-i); 

Quando avrebbe dovuto essere:

count=count+(mid-i+1); 

Come dobbiamo sottrarre dagli elementi lasciati sul lato sinistro della serie "dopo" l'ordinamento non inizialmente quando la subroutine viene chiamata poiché l'indice cambia dopo l'ordinamento. Sto scrivendo il mio codice aggiornato nel caso in cui se qualcuno sarebbe finito in un problema simile come il mio:

static int [] helper; 
static long count=0; 
static Integer [] arr3; 

private static void mergeSortMethod(Integer[] arr3) { 
    int head=0; 
    int tail=arr3.length-1; 
    int mid=tail+((head-tail)/2); 

    sort(arr3,head,tail); 
} 


private static void sort(Integer[] arr3, int low, int high) { 

    if (high<=low){ 
     return; 
    } 
    int mid=low+ ((high-low)/2); 

    sort(arr3,low,mid); 
    sort(arr3,mid+1,high); 

    merge3CountInvs(arr3,low,mid,high); 

} 

private static void merge3CountInvs(Integer[] arr3, int low, int mid, int high) { 
    int i=low; 
    int j=mid+1; 
    int k=low; 

    for (int m=low;m<=high;m++){ 
     helper[m]=arr3[m]; 

    } 

    while(i < mid+1 && j < high+1){// neither array empty 
     if(helper[i] < helper[j]){ 
      arr3[k++] = helper[i++]; 

     } 

     else if (helper[j] < helper[i]){ 
      arr3[k++] = helper[j++]; 
     //to increment count with total number of elements left in arrayA after sorting 
      count=count+(mid-i+1); 

     } 
    } 
    while(i < mid+1){ // arrayB is empty, 
     arr3[k++] = helper[i++]; 
    } 

    while(j < high+1){ // arrayA is empty, 
     arr3[k++] = helper[j++]; 
    } 

} 

Answer 1

Il mio codice funziona correttamente per i tuoi dati e sto ottenendo risultati perfettamente corretti. Si prega di confrontare con esso e controllare ciò che sta facendo male nell'algoritmo

public static void main(String[] args){ 
      int[] dataInv = new int[100000]; 
      Random rand = new Random(); 
      for (int i = 0; i < dataInv.length; i++) { 
       dataInv[i] = rand.nextInt(); 
      } 

      System.out.println("Inversions: " + numberOfInversions(dataInv)); 
    } 

    private static long numberOfInversions(int[] data) { 
     int[] temp = new int[data.length]; 
     return mergeSort(data, temp, 0, data.length - 1); 
    } 

    private static long mergeSort(int[] data, int[] temp, int low, int high) { 
     long inversions = 0L; 
     if (high > low) { 

      int mid = (high + low)/2; 

      inversions = mergeSort(data, temp, low, mid); 
      inversions += mergeSort(data, temp, mid + 1, high); 

      inversions += merge(data, temp, low, mid + 1, high); 
     } 

     return inversions; 
    } 

    private static long merge(int[] data, int[] temp, int low, int mid, int high) { 
     int i, j, k = 0; 
     long invertions = 0L; 

     i = low; 
     j = mid; 
     k = low; 

     while (i <= (mid - 1) && j <= high) { 
      if (data[i] <= data[j]) { 
       temp[k++] = data[i++]; 
      } else { 
       temp[k++] = data[j++]; 

       invertions += (mid - i); 
      } 
     } 

     while (i <= (mid - 1)) { 
      temp[k++] = data[i++]; 
     } 

     while (j <= high) { 
      temp[k++] = data[j++]; 
     } 

     for (i = low; i <= high; i++) { 
      data[i] = temp[i]; 
     } 

     return invertions; 

    } 

Answer 2

Stai cercando di memorizzare un numero maggiore di Integer.MAX_VALUE - provare a utilizzare un long invece

Answer 3

È stiamo usando numeri che non si adattano a numeri interi a 32 bit e quindi si ha un overflow. Utilizza long per risultati inferiori a 2^63 o java.math.BigInteger per tutti i possibili numeri interi che si adattano alla tua memoria.

Answer 4

Pensa a questo: Supponi di chiamare sort() sul sottoarray dove basso = 99990 e alto = 99999. Quindi metà = 99994. In merge3CountInvs(), cosa saranno nArr1Elems? Quale gamma di valori assumerà "io"? Cosa verrà aggiunto per contare nella dichiarazione

 count=count+(nArr1Elems-i); 

?