Считая инверсии для массива из 100 000 целых чисел, зачем получать отрицательный результат? - PullRequest
Новая
       13

Считая инверсии для массива из 100 000 целых чисел, зачем получать отрицательный результат?

2 голосов
/ 26 марта 2012 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;


public class InversionCounter {
    public static void main(String[] args) {
        Scanner scanner = null;
        try {
            scanner = new Scanner(new File("src/IntegerArray.txt"));
        } catch (FileNotFoundException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        int [] nums = new int [100000];
        int i = 0;
        while(scanner.hasNextInt()){
           nums[i++] = scanner.nextInt();
        }
        System.out.println(countInversions(nums));

    }

public static int countInversions(int[] nums) {
    int count = 0;
    for (int i=0;i<nums.length-1;i++) {
        for (int j=i+1;j<nums.length;j++) {
            if (nums[i]>nums[j]) {
                count++;
            }
            else {continue;}
        }
    }
    return count;
}

}

Приведенный выше код считывает 100 000 целых чисел из файла и считает обращения для этого массива целых чисел. Вывод, вероятно, очень большой, например, 1198233847, и определенно должен быть положительным. Тем не менее, он выводит отрицательный, как -1887062008. Логика программы, вероятно, будет правильной, так как я пробовал другие алгоритмы для той же цели и получил то же отрицательное число, что и вывод. Я подозреваю, что в результате получается слишком большое положительное число, и в результате Java преобразует его в отрицательное.

Ответы [ 2 ]

3 голосов
/ 26 марта 2012

Максимальное значение int составляет 2 147 483 647 - то, что вы видите, является переполнением.Вы должны сделать count a long, если вы ожидаете, что он будет таким большим.

source: http://docs.oracle.com/javase/tutorial/java/nutsandbolts/datatypes.html

2 голосов
/ 26 марта 2012

Наихудший случай здесь - 4 999 950 000 инверсий, что больше, чем максимальное значение int (2 147 483 647).Вам, вероятно, следует использовать long для хранения номера.

...