[LintCode] Reverse Pairs

tigerZH 发布于2019-08-14 15:33 / 880人阅读

摘要：暴力解法就是时灵时不灵，两次一次。希望看到的大神能够分享优质的解法谢谢大家

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, 5] , (2, 1), (4, 1), (4, 3) are reverse pairs. return 3

Note

暴力解法就是时灵时不灵，submit两次ac一次。
希望看到的大神能够分享优质的解法^_^ linspiration1991@gmail.com

Solution

public class Solution {
    public long reversePairs(int[] A) {
        long res = 0;
        int n = A.length;
        for (int i = 0; i < n-1; i++) {
            for (int j = i; j < n; j++) {
                if (A[i] > A[j]) res += 1;
            }
        }
        return res;
    }
}
//谢谢大家！

GPU云服务器云服务器 pairs LintCode Reverse LintCode134_LRU

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

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

[LeetCode/LintCode] Top K Frequent Words

LeetCode version Problem Given a non-empty list of words, return the k most frequent elements. Your answer should be sorted by frequency from highest to lowest. If two words have the same frequency, t...

0x584a 2019-08-15 13:32 评论0 收藏0
两数之和问题各变种多解法小结

摘要：两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处两数之和等于题目大意给出未排序数组和指定目标，返回数组中两数之和的组合元素下标要求下标从开始，而且，保证题目中有且只有个可行解解法暴力时间复杂度求解解题思路暴力二重循环求解两数之和问题各变种多解法小结声明文章均为本人技术笔记，转载请注明出处：[1] https://segmentfault.com/u/yzwal...

lentoo 2019-08-16 10:34 评论0 收藏0
[LintCode] K-diff Pairs in an Array

Problem Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both nu...

Leck1e 2019-08-15 18:16 评论0 收藏0
[LeetCode/LintCode] Sentence Similarity

Problem Given two sentences words1, words2 (each represented as an array of strings), and a list of similar word pairs pairs, determine if two sentences are similar. For example, great acting skills a...

dreamtecher 2019-08-16 12:44 评论0 收藏0
[LintCode] Swap Nodes in Pairs

摘要：指针为，我们选择的两个结点是和。要注意循环的边界条件，这两个结点不能为空。主要思路是先用和两个新结点去保存和两个结点。完成交换之后，连接和，并让前进至此时的结点。 Problem Given a linked list, swap every two adjacent nodes and return its head. Example Given 1->2->3->4, you sh...

EscapedDog 2019-08-14 15:11 评论0 收藏0