493. Reverse Pairs

acrazing 发布于2019-08-14 17:36 / 1207人阅读

摘要：题目链接和还有是一类题，解法都差不多。可以做，但是这道题如果输入是有序的，简单的会超时，所以得用来做。算的方法是比如给的例子，现在分成了左右两部分，拿两个指针和。

493. Reverse Pairs

题目链接：
https://leetcode.com/problems...

和Count of Smaller Numbers After Self还有count of range sum是一类题，解法都差不多。BST可以做，但是这道题如果输入是有序的，简单的bst会超时，所以得用AVL来做。
然后就是binary index tree的做法，计算大于nums[j]2的时候就是拿全部的sum减去sum(nums[j] 2)

public class Solution {
    public int reversePairs(int[] nums) {
        int res = 0;
        int n = nums.length;
        if(n == 0) return res;
        // reflection
        Map map = new HashMap();
        long[] sorted = new long[2*n];
        for(int i = 0; i < n; i++) {
            sorted[2*i] = nums[i];
            sorted[2*i + 1] = (long) nums[i] * 2;
        }
        Arrays.sort(sorted);
        int idx = 1;
        for(long num : sorted) {
            if(!map.containsKey(num)) map.put(num, idx++);
        }
        
        BIT t = new BIT(idx);
        int sum = 0;
        for(int j = 0; j < n; j++) {
            // find how many number > 2 * nums[j]
            long num = (long) nums[j];
            res += sum - t.sum(map.get(num*2));
            t.add(map.get(num), 1);
            sum++;
        }
        return res;
    }
    
    class BIT {
        int n;
        int[] tree;
        BIT(int n) { this.n = n; tree = new int[n]; }
        
        protected int sum(int i) {
            int res = 0;
            while(i > 0) {
                res += tree[i];
                i -= i & -i;
            }
            return res;
        }
        
        protected void add(int i, int val) {
            while(i < n) {
                tree[i] += val;
                i += i & -i;
            }
        }
    }
}

merge sort的做法，同样是每次要统计左边有多少结果是 > 2 * nums[j]的，每次sort完之后先算有多少pairs再merge。算pairs的方法是：
比如给的例子，现在分成了左右两部分[1, 1, 2], [3, 3]，拿两个指针i和j。

if nums[i]/2.0 > nums[j]，表示所有小与等于nums[j]的值都满足这个条件，一直增大到不满足条件的，最后j - (mid+1)就是全部满足该条件且包含nums[i]的pair数目

else, 表示nums[i]小了，需要i++

loop的invariant用包含nums[j]的也行：

ifnums[i]/2.0 > nums[j]表示所有大于等于nums[i]的都满足条件，res += mid - i + 1，同时j++

else表示i小了，所以i++

每次重新开一个aux就超时了，所以把aux当全局变量，开一次

public class Solution {
    public int reversePairs(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        
        // merge sort
        res = 0;
        aux = new int[n];
        sort(nums, 0, n - 1);
        return res;
    }
    int res;
    int[] aux;
    
    private void sort(int[] nums, int l, int r) {
        if(l >= r) return;
        int mid = l + (r - l) / 2;
        sort(nums, l, mid);
        sort(nums, mid + 1, r);
        int i = l, j = mid + 1;
        while(j <= r) {
            while(i <= mid && nums[i]/2.0 <= nums[j]) i++;
            // count number of pairs include nums[j]
            res += mid - i + 1;
            j++;
        }
        merge(nums, l, mid, r);
    }
    
    private void merge(int[] nums, int l, int mid, int r) {
        for(int k = l; k <= r; k++) aux[k] = nums[k];
        
        int i = l, j = mid + 1;
        for(int k = l; k <= r; k++) {
            if(i > mid) nums[k] = aux[j++];
            else if(j > r) nums[k] = aux[i++];
            else if(aux[i] > aux[j]) nums[k] = aux[j++];
            else nums[k] = aux[i++];
        }
    }
}

云服务器 GPU云服务器 pairs Reverse reverse-proxy reverse-integer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66698.html

336. Palindrome Pairs

摘要：容易出的两个地方以为例。这两个互为的在尾部加上也就是在头部加上所以后部分不能为空，否则就和头部为空的情况重复了。空间复杂度因为用了额外的来储存，需要空间。时间复杂度每个分为两个部分，调用前后两部分总长度为所以每次调用为一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...

Guakin_Huang 2019-08-14 17:57 评论0 收藏0
[LintCode] Reverse Pairs

摘要：暴力解法就是时灵时不灵，两次一次。希望看到的大神能够分享优质的解法谢谢大家 Problem For an array A, if i < j, and A[i] > A[j], called (A[i], A[j]) is a reverse pair.return total of reverse pairs in A. Example Given A = [2, 4, 1, 3, ...

tigerZH 2019-08-14 15:33 评论0 收藏0
【LC总结】翻转链表 Swap in Pairs, Reverse in k-Group, Reve

摘要：注意这里，只要走到第位 Swap Nodes in Pairs For example,Given 1->2->3->4, you should return the list as 2->1->4->3. Solution public class Solution { public ListNode swapPairs(ListNode head) { if...

Steve_Wang_ 2019-08-14 14:55 评论0 收藏0
[Leetcode] Swap Nodes in Pairs Reverse Nodes in k-

摘要：三指针法复杂度时间空间思路基本的操作链表，见注释。注意使用头节点方便操作头节点。翻转后，开头节点就成了最后一个节点。 Swap Nodes in Pairs Given a linked list, swap every two adjacent nodes and return its head. For example, Given 1->2->3->4, you should ...

TZLLOG 2019-08-14 12:45 评论0 收藏0
Palindrome Pairs & Shortest Palindrome

摘要：部分是回文的，在里面找是否有的。这里的范围是，最小是，因为要保证是两个单词，最大是，这时候要找出另一个和他相反的串。判断为回文，可以直接暴力，每个都判断一次。两个方向都找一遍就可能出现重复的情况，注意避免重复。例如，结果应该是。 Palindrome Pairs 链接：https://leetcode.com/problems... 这道题没想出来思路，参考了这个博客的内容：http:...

CNZPH 2019-08-14 17:20 评论0 收藏0