数组逆序对计数算法输出错误,求代码问题排查与修正方案
代码错误原因排查
- 核心错误:静态计数变量未重置
你使用静态全局变量count统计逆序对数量,但inversionCount方法每次被调用时没有将count重置为0。在线评测平台会复用类实例运行多组测试用例,上一组用例的计数结果会残留到后续用例中,直接导致输出结果偏大。 - 次要问题:merge方法存在冗余代码
merge方法中写了两次遍历left数组剩余元素的循环,第二次循环永远不会触发,属于无用代码,虽不影响计算结果,但属于逻辑疏漏。 - 非强制规范问题
所有数组索引变量(i、j、k、lo、hi、mid)均使用long类型,Java中数组长度本身为int类型,反复强转没有必要,直接使用int类型即可。
修正后代码
class Solution { static long count = 0; static long inversionCount(long arr[], long n) { count = 0; // 新增代码:每次调用前重置计数 long merged[] = mergeSort(arr, 0, n - 1); return count; } static long[] merge(long left[], long right[]) { long res[] = new long[left.length + right.length]; long i = 0, j = 0, k = 0; while (i < left.length && j < right.length) { if (left[(int)i] <= right[(int)j]) { res[(int)k] = left[(int)i]; k++; i++; } else { count = count + (left.length - i); res[(int)k] = right[(int)j]; k++; j++; } } while (i < left.length) { res[(int)k] = left[(int)i]; i++; k++; } while (j < right.length) { res[(int)k] = right[(int)j]; k++; j++; } // 删除了重复的left剩余元素复制循环 return res; } static long[] mergeSort(long a[], long lo, long hi) { if (hi == lo) { long temp[] = {a[(int)hi]}; return temp; } long mid = (hi + lo) / 2; long left[] = mergeSort(a, lo, mid); long right[] = mergeSort(a, mid + 1, hi); return merge(left, right); } }
内容的提问来源于stack exchange,提问作者Sachin
相关产品推荐
相关产品推荐

