LeetCode 493. 翻转对

你的名字 2022-10-29 03:13 122阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]

//解法一：分治 真tm慢 才5%
    class Solution {
        
        public int reversePairs(int[] nums) {
        
            if(nums.length == 0){
        
                return 0;
            }
            return reversePairRecursive(nums, 0, nums.length - 1);
        }
    
        public int reversePairRecursive(int[] nums, int left, int right){
        
            if(left == right){
        
                return 0;
            }else{
        
                int mid = left + (right - left) / 2;
                int n1 = reversePairRecursive(nums,left,mid);
                int n2 = reversePairRecursive(nums,mid + 1,right);
                int ret = n1 + n2;
    
                //首先统计下标对的数量
                int i = left;
                int j = mid + 1;
                while(i <= mid){
        
                    while(j <= right && (long) nums[i] > 2 * (long) nums[j]){
        
                        j++;
                    }
                    ret += j - mid - 1;
                    i++;
                }
                System.out.println(ret);
                int[] sorted = new int[right - left + 1];
                int p1 = left, p2 = mid + 1;
                int p = 0;
                while(p1 <= mid || p2 <= right){
        
                    if(p1 > mid){
        
                        sorted[p++] = nums[p2++];
                    }else if(p2 > right){
        
                        sorted[p++] = nums[p1++];
                    }else{
        
                        if(nums[p1] < nums[p2]){
        
                            sorted[p++] = nums[p1++];
                        }else{
        
                            sorted[p++] = nums[p2++];
                        }
                    }
                }
                for(int k = 0;k < sorted.length;k++){
        
                    nums[left + k] = sorted[k];
                }
                //System.out.println(ret);
                return ret;
            }
        }
    }

//解法二：树状数组 13%
    class Solution {
        
        public int reversePairs(int[] nums) {
        
            Set<Long> allNumbers = new TreeSet<Long>();
            for(int x : nums){
        
                allNumbers.add((long)x);
                allNumbers.add((long)x * 2);
            }
            Map<Long, Integer> values = new HashMap<Long, Integer>();
            int idx = 1;
            for(long x : allNumbers){
        
                values.put(x, idx);
                idx++;
            }
            int ret = 0;
            BIT bit = new BIT(values.size() + 1);
            for(int i = 0; i < nums.length; i++){
        
                int left = values.get((long)nums[i] * 2), right = values.size();
                ret += bit.query(right) - bit.query(left);
                bit.update(values.get((long)nums[i]), 1);
            }
            return ret;
        }
    }
    
    class BIT {
        
        int[] tree;
        int n;
    
        public BIT(int n) {
        
            this.n = n;
            this.tree = new int[n + 1];
        }
    
        public static int lowbit(int x) {
        
            return x & (-x);
        }
    
        public void update(int x, int d) {
        
            while (x <= n) {
        
                tree[x] += d;
                x += lowbit(x);
            }
        }
    
        public int query(int x) {
        
            int ans = 0;
            while (x != 0) {
        
                ans += tree[x];
                x -= lowbit(x);
            }
            return ans;
        }
    }

//解法三：线段树  5% 好拉跨
    class Solution {
        
        public int reversePairs(int[] nums) {
        
            Set<Long> allNumbers = new TreeSet<Long>();
            for(int x : nums){
        
                allNumbers.add((long)x);
                allNumbers.add((long)x * 2);
            }
            System.out.println(allNumbers.size());
            Map<Long, Integer> values = new HashMap<Long, Integer>();
            int idx = 0;
            for(long x : allNumbers){
        
                values.put(x, idx);
                idx++;
            }
            int ret = 0;
            int[] a = new int[values.size()];
            TreeNode root = buildTree(a, 0, values.size() - 1);
            for(int i = 0; i < nums.length; i++){
        
                int left = values.get((long)nums[i] * 2) + 1, right = values.size() - 1;
                ret += queryTree(root, left, right);
                updateTree(root, values.get((long)nums[i]), 1);
            }
            return ret;
        }
    
        class TreeNode {
        
            int val;
            int start;
            int end;
            TreeNode left;
            TreeNode right;
    
            public TreeNode(int start, int end) {
        
                left = null;
                right = null;
                this.start = start;
                this.end = end;
            }
        }
    
        private TreeNode buildTree(int[] nums, int start, int end) {
        
            if (start > end) return null;
            TreeNode curr = new TreeNode(start, end);
            if (start == end) curr.val = nums[start];
            else {
        
                int mid = start + (end - start) / 2;
                curr.left = buildTree(nums, start, mid);
                curr.right = buildTree(nums, mid + 1, end);
                curr.val = curr.left.val + curr.right.val;
            }
            return curr;
        }
    
        public void updateTree(TreeNode node, int i, int val) {
        
            if (node.start == node.end) {
        
                node.val += val;
            } else {
        
                int mid = node.start + (node.end - node.start) / 2;
                if (i <= mid) updateTree(node.left, i, val);
                else updateTree(node.right, i, val);
                node.val = node.left.val + node.right.val;
            }
        }
    
        public int queryTree(TreeNode node, int i, int j) {
        
            if(i > j)
                return 0;
            if (node.start >= i && node.end <= j) return node.val;
            else {
        
                int mid = node.start + (node.end - node.start) / 2;
                if (j <= mid) {
        
                    return queryTree(node.left, i, j);
                } else if (i >= (mid + 1)) {
        
                    return queryTree(node.right, i, j);
                } else {
        
                    return queryTree(node.left, i, mid) + queryTree(node.right, mid + 1, j);
                }
            }
        }
    
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zODE5OTc3MA_size_16_color_FFFFFF_t_70]: /images/20221024/54c2eb9b71d1485d8bd364e82987be6f.png