LeetCode Top Interview Questions 315. Count of Smaller Numbers After Self (Java版； Hard)

爱被打了一巴掌 2023-07-02 08:24 23阅读 0赞

### [welcome to my blog][] ###

## LeetCode Top Interview Questions 315. Count of Smaller Numbers After Self (Java版; Hard) ##

#### 题目描述 ####

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].
    
    Example:
    
    Input: [5,2,6,1]
    Output: [2,1,1,0] 
    Explanation:
    To the right of 5 there are 2 smaller elements (2 and 1).
    To the right of 2 there is only 1 smaller element (1).
    To the right of 6 there is 1 smaller element (1).
    To the right of 1 there is 0 smaller element.

####  ####

class Solution { 
        public List<Integer> countSmaller(int[] nums) { 
            List<Integer> list = new ArrayList<>();
            int n = nums.length;
            if(n==0){ 
                return list;
            }
            //对索引进行归并排序, 根据索引对应的值的大小进行条件划分
            int[] index = new int[n];
            for(int i=0; i<n; i++){ 
                index[i] = i;
                list.add(0);
            }
            //
            mergeSort(list, nums, index, 0, n-1);
            return list;
            
        }
    
        private void mergeSort(List<Integer> list, int[] nums, int[] index, int L, int R){ 
            if(L>=R){ 
                return;
            }
            int mid = L + (R - L)/2;
            mergeSort(list, nums, index, L, mid);
            mergeSort(list, nums, index, mid+1, R);
            merge(list, nums, index, L, mid, R);
        }
    
        private void merge(List<Integer> list, int[] nums, int[] index, int L, int mid, int R){ 
            int[] help = new int[R-L+1];
            int p1=L, p2=mid+1, p=0;
            int count=0;
            while(p1<=mid && p2<=R){ 
                //右部分小
                if(nums[index[p1]] > nums[index[p2]]){ 
                    help[p++] = index[p2++];
                    count++;
                //左部分小
                }else{ 
                    help[p++] = index[p1];
                    //
                    list.set(index[p1], list.get(index[p1])+count);
                    p1++;
                }
            }
            while(p1<=mid){ 
                help[p++] = index[p1];
                list.set(index[p1], list.get(index[p1])+count);
                p1++;
            }
            while(p2<=R){ 
                help[p++] = index[p2++];
            }
            for(int i=0; i<help.length; i++){ 
                index[L+i] = help[i];
            }
    
        }
    }

#### 第一次做, 只能想到暴力的方法, 于是直接看的题解, 明白了思想后自己便能写出来了, 用的是归并排序的思想, 之前做过类似的题, 求的是逆序对的数量, 这道题更难一些, 因为并不是对nums进行归并排序, 而是对indexMap进行归并排序. indexMap记录的是原始索引所在的位置的信息. 归并排序中根据nums中元素的大小分成两种情况; 核心: 归并排序会把数组分成两部分处理, 右部分小的时候count++, 左部分小的时候更新对应的res. 在纸上写个例子模拟一遍流程就清楚了, 比如\[5,2,6,1\]; 细节: 单独需要注意的是mergesort中的if条件句是left>=right, 因为会有left>right的情况, 当nums.length==0时, left=0, right=-1, 所以要么在input check中检查length, 要么把这个if条件改成left>=right ####

class Solution { 
        public List<Integer> countSmaller(int[] nums) { 
            List<Integer> result = new ArrayList<>();
            if(nums==null)
                return result;
            //
            //索引映射, 原始索引与新索引的对应关系, 新索引会改变
            int n = nums.length;
            int[] indexMap = new int[n];
            for(int i=0; i<n; i++){ 
                indexMap[i] = i;
            }
            //临时结果
            int[] res = new int[n];
            //对indexMap进行归并排序
            mergesort(res, nums, indexMap, 0, n-1);
            //把res的结果给result
            for(int a : res){ 
                result.add(a);
            }
            return result;
            
        }
        public void mergesort(int[] res, int[] nums, int[] indexMap, int left, int right){ 
            //会有left>right的情况吗? 有, 当nums.length==0时, left=0, right=-1, 所以要么在input check中检查length, 要么把这个if条件改成left>=right
            if(left>=right)
                return;
            int mid = left + ((right-left)>>1);
            mergesort(res, nums, indexMap, left, mid);
            mergesort(res, nums, indexMap, mid+1, right);
            merge(res,nums,indexMap,left,mid,right);
        }
        public void merge(int[] res, int[] nums, int[] indexMap, int left, int mid, int right){ 
            int[] help = new int[right-left+1];
            int p1 = left, p2 = mid+1, p=0;
            int count = 0;
            while(p1<=mid && p2<=right){ 
                //如果右部分的小
                if(nums[indexMap[p1]] > nums[indexMap[p2]]){ 
                    help[p++] = indexMap[p2++];
                    count++;
                }
                //如果左部分的小
                else{ 
                    help[p++] = indexMap[p1];
                    res[indexMap[p1++]] += count;
                }
            }
            //如果左部分还有没处理的
            while(p1<=mid){ 
                help[p++] = indexMap[p1];
                res[indexMap[p1++]] += count;
            }
            //如果右部分还有没处理的
            while(p2<=right){ 
                help[p++] = indexMap[p2++];
                //此时不需要再更新count了
            }
            //将help的结果更新给indexMap
            for(int i=0; i<right-left+1; i++){ 
                indexMap[left+i] = help[i];
            }
        }
    }

[welcome to my blog]: https://littlehaes.com