数组逆序数计算Java代码报错：数组索引越界问题排查

问题背景 #

数组逆序数定义：对于数组中所有下标i、j（均小于数组长度），当i < j时，满足A[j] < A[i]的(A[i], A[j])对即为逆序对。
输入示例：N=5，数组={5,3,2,1,4}，预期结果为7，对应7个逆序对：(5,3)、(5,2)、(5,1)、(5,4)、(3,2)、(3,1)、(2,1)。

代码与报错 #

尝试用单循环实现逆序数计算逻辑，编写了如下Java代码，但运行时抛出数组越界异常：

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -1 out of bounds for length 5 at Main.main(Main.java:14)

手动推演逻辑时认为正确，但实际运行报错，需排查问题。

附原代码：

//数组逆序数定义：对于所有i & j < 数组长度，若i < j，找出满足A[j] < A[i]的(A[i], A[j])对。
//输入格式
//: N = 5, array[] = {5,3,2,1,4}
//结果
//: 7
//解释
//: 共有7个符合条件的对：(5,1), (5,3), (5,2), (5,4),(3,2), (3,1), (2,1)，而(2,4)和(1,4)不满足条件，故不计入。

import java.io.*;
import java.util.*;
class Main
{
    public static void main(String args[])
    {
        int[] arr = {5,3,2,1,4};
        int l = arr.length;
        int i = 0,count = 0,j = l-1;
        while(i < l-1)
        {
            if(j==i)
                i++;
            else if(arr[i] > arr[j])
            {
                count++;
                j--;
            }
            else
                j--;
        }
        System.out.print(count);
    }
}

问题分析 #

报错核心是数组下标越界，根源在于两处逻辑错误：

1. 当j递减到与i相等时，代码仅将i加1，但未重置j为数组末尾（l-1），导致后续j继续递减至-1，访问arr[j]触发异常。
2. 原逻辑违背逆序数定义：逆序数要求统计i < j时的符合条件对，但代码中j从末尾向i方向遍历，实际统计的是j < i的情况，即使修复越界问题，计算结果也会错误。

修复后的代码 #

嵌套循环实现（逻辑清晰） #

对每个i，遍历所有j > i的元素，统计满足A[j] < A[i]的数量：

import java.io.*;
import java.util.*;
class Main
{
    public static void main(String args[])
    {
        int[] arr = {5,3,2,1,4};
        int l = arr.length;
        int count = 0;
        // 遍历每个i，检查所有j > i的元素
        for(int i = 0; i < l; i++){
            for(int j = i + 1; j < l; j++){
                if(arr[i] > arr[j]){
                    count++;
                }
            }
        }
        System.out.print(count); // 输出7，符合预期
    }
}

单while循环实现 #

若坚持使用单while循环，需重置j的位置以符合i < j的遍历逻辑：

import java.io.*;
import java.util.*;
class Main
{
    public static void main(String args[])
    {
        int[] arr = {5,3,2,1,4};
        int l = arr.length;
        int i = 0, count = 0, j = i + 1;
        while(i < l){
            if(j < l){
                if(arr[i] > arr[j]){
                    count++;
                }
                j++;
            } else {
                i++;
                j = i + 1; // 重置j为i的下一个位置
            }
        }
        System.out.print(count); // 输出7
    }
}

结果验证 #

修复后的代码运行后输出7，与预期结果一致，正确统计了所有符合定义的逆序对。

内容的提问来源于stack exchange，提问作者Ashish Kumar