【剑指offer-Java版】36数组中的逆序对

- 日理万妓 2022-08-21 09:48 90阅读 0赞

数组中的逆序对：归并排序的另类应用

数组中的逆序对：给定的数组，如果两个数字中前面一个数字大于后面的一个，那么称为一个逆序对，数组中所有满足此关系的逆序对总数就是这个数组的逆序对

此处的实现并不优雅，毕竟copy数组是不需要的，只需要一个局部的就可以  
但是如果使用的是一个局部的空间复杂度是logn的辅助数组，会造成代码有一点点难理解

另外，书上的明显是错误的代码，没有运行过，但是从逻辑上来分析，应该会出现重复统计的问题

public class _Q36<T> {
    
        public int InversePairs(int nums[]){
            if(nums == null) return 0;
            int copy[] = Arrays.copyOf(nums, nums.length);
            CommonUtils.PrintArray(copy);
            return InversePairsCore(nums, copy, 0, nums.length - 1);
        }
    
        private int InversePairsCore(int nums[], int copy[], int indexL, int indexR){
            if(nums == null || indexL > indexR) return 0;
    
            if (indexL == indexR) {
                //copy[indexL] = nums[indexL];
                return 0;
            }
    
            int len = (indexR - indexL) / 2;
    
            int leftCount = InversePairsCore(nums, copy, indexL, indexL + len);
            int rightCount = InversePairsCore(nums, copy, indexL + len + 1, indexR);
    
            int i = indexL + len;
            int j = indexR;
            int indexCopy = indexR;
            int count = 0;
            while(i >= indexL && j >= indexL + len + 1){
                if(nums[i] > nums[j]){ // 出现逆序对
                    copy[indexCopy--] = nums[i--];
                    count = count + j - len - indexL;
                }else{
                    copy[indexCopy--] = nums[j--];
                }
            }
    
            while(i >= indexL) copy[indexCopy--] = nums[i--];
            while(j >= indexL + len + 1) copy[indexCopy--] = nums[j--];
    
            for(int k=indexL; k<=indexR; k++){
                nums[k] = copy[k];
            }
    
            CommonUtils.PrintArray(copy);
    
            return leftCount + count + rightCount;
        }
        }

测试代码：

public class _Q36Test extends TestCase {
        
    
        _Q36 inversePair = new _Q36();
    
        public void test(){
            int array[] = {
       7, 5, 6, 4};
    
            System.out.println(inversePair.InversePairs(array));
        }
        }