[Swift]LeetCode493. 翻转对 | Reverse Pairs

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j].

You need to return the number of important reverse pairs in the given array.

Example1:

Input: [1,3,2,3,1]
Output: 2 

Example2:

Input: [2,4,3,5,1]
Output: 3 

Note:

  1. The length of the given array will not exceed 50,000.
  2. All the numbers in the input array are in the range of 32-bit integer.


给定一个数组 nums ,如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对

你需要返回给定数组中的重要翻转对的数量。

示例 1:

输入: [1,3,2,3,1]
输出: 2

示例 2:

输入: [2,4,3,5,1]
输出: 3

注意:

  1. 给定数组的长度不会超过50000
  2. 输入数组中的所有数字都在32位整数的表示范围内。

Runtime: 1632 ms

Memory Usage: 20.3 MB

 1 class Solution {
 2     func reversePairs(_ nums: [Int]) -> Int {
 3         var res:Int = 0
 4         var copy:[Int] = nums.sorted(by:<)
 5         var bit:[Int] = [Int](repeating:0,count:copy.count + 1)
 6         for ele in nums
 7         {
 8             res += search(&bit, index(copy, 2 * ele + 1))
 9             insert(&bit, index(copy, ele))
10         }
11         return res
12     }
13
14     func index(_ arr:[Int],_ val:Int) -> Int
15     {
16         var l:Int = 0
17         var r:Int = arr.count - 1
18         var m:Int = 0
19         while(l <= r)
20         {
21             m = l + ((r - l) >> 1)
22             if arr[m] >= val
23             {
24                 r = m - 1
25             }
26             else
27             {
28                 l = m + 1
29             }
30         }
31         return l + 1
32     }
33
34     func search(_ bit:inout [Int],_ i:Int) -> Int
35     {
36         var i = i
37         var sum:Int = 0
38         while(i < bit.count)
39         {
40             sum += bit[i]
41             i += i & -i
42         }
43         return sum
44     }
45
46     func insert(_ bit:inout [Int],_ i:Int)
47     {
48         var i = i
49         while(i > 0)
50         {
51             bit[i] += 1
52             i -= i & -i
53         }
54     }
55 }

原文地址:https://www.cnblogs.com/strengthen/p/10348715.html

时间: 02-02

[Swift]LeetCode493. 翻转对 | Reverse Pairs的相关文章

[LeetCode] Reverse Pairs 翻转对

Given an array nums, we call (i, j) an important reverse pair if i < j and nums[i] > 2*nums[j]. You need to return the number of important reverse pairs in the given array. Example1: Input: [1,3,2,3,1] Output: 2 Example2: Input: [2,4,3,5,1] Output:

LeetCode -Reverse Pairs

my solution: class Solution { public: int reversePairs(vector<int>& nums) { int length=nums.size(); int count=0; for (int i=0;i<length;i++) { for(int j=i+1;j<length;j++) { if(nums[i]>2*nums[j]) count++; } } return count; } }; wrong answ

【leetcode】493. Reverse Pairs

好吧这其实是一次小比赛,在回上海前的周末.好久没打比赛,简单题也只是AK了而已,还TM错了一次.最后45名57分钟加一次罚时,第一名18分钟,好吧.也行了对于业余组选手. 错在没考虑到乘2会超max_int. 程序没了,也没心情找了.孤单的情人节. 貌似有两个人被发现作弊了我变成了43名,还找到了程序,也算一点小小的安慰吧. class Solution { public: int reversePairs(vector<int>& aa) { vector<long long&

笔试算法题(07):还原后序遍历数组 &amp; 半翻转英文句段

出题:输入一个整数数组,判断该数组是否符合一个二元查找树的后序遍历(给定整数数组,判定其是否满足某二元查找树的后序遍历): 分析:利用后序遍历对应到二元查找树的性质(序列最后一个元素必定是根节点,从左向右第一个比根节点大的元素开始直到根节点之前的所有元素必定在右子树,之前的所有元素必定在左子树): 解题: 1 bool PostOrderCheck(int *array, int i, int j) { 2 /** 3 * 如快速排序一样,解决小子文件 4 * */ 5 if(j-i+1 ==

python2.0_s12_day13_javascript&amp;Dom&amp;jQuery

今天主要内容:JavaScriptDomjQuery http://www.cnblogs.com/wupeiqi/articles/5369773.html 今天主要内容大致了解:javascript 1.首先要知道 JavaScript 和 Java 没有半毛钱关系. 2.JavaScript 和python语言 一样 它也是一门语言.对于python语言需要用python解释器解释.而javascript的解释器是浏览器. 3.javascript 能实现什么.javascript就是让我

应用及函数

--select*from 名 order by 列 asc --升序排列--select*from 名 order by 列 desc --降序排列--select distinct 列 from 名 --去重--select 列 from 名 group by 列 --分组--函数--select avg(列) as '列名' from 名--平均值--select max(列)/ min(列)as '最大'/as'最小' from 名 --最大/最小值--select 列,count(*)

redis源码分析3---结构体---字典

redis源码分析3---结构体---字典 字典,简单来说就是一种用于保存键值对的抽象数据结构: 注意,字典中每个键都是独一无二的:在redis中,内部的redis的数据库就是使用字典作为底层实现的: 1 字典的实现 在redis中,字典是使用哈希表作为底层实现的,一个hash表里面可以有多个hash表节点,而每个hash表节点就保存了字典中的一个键值对: hash表定义 table属性是一个数组,数组中的每个元素都是一个指向dictEntry结构的指针,每个dictEntry结构保存着一个键值

Java基础Map接口+Collections

1.Map中我们主要讲两个接口 HashMap  与   LinkedHashMap (1)其中LinkedHashMap是有序的  怎么存怎么取出来 我们讲一下Map的增删改查功能: /* * Map集合的添加 */ Map<String, String> map = new HashMap<String, String>(); map.put("星期一", "Monday"); map.put("星期六", "

JavaScript笔录

JavaScript是一门编程语言,浏览器内置了JavaScript语言的解释器,所以在浏览器上按照JavaScript语言的规则编写相应代码之,浏览器可以解释并做出相应的处理. 1.JavaScript代码存在形式 <!-- 方式一 --> <script type"text/javascript" src="JS文件"></script> <!-- 方式二 --> <script type"text

SQL-数学、字符串、时间日期函数和类型转换

--数学函数 --ABS绝对值,select ABS(-99)--ceiling取上限,select CEILING(4.5)--floor去下限select FLOOR(4.5)--power 几次方,select POWER(2,2)--round四舍五入,select round (6.45,1)--sqrt开平方select SQRT(9)--square平方select SQUARE(5) --字符串函数--ASCII 返回字符串最左边的字符ascii码select ASCII('na