摘要:題目鏈接和還有是一類題,解法都差不多。可以做,但是這道題如果輸入是有序的,簡(jiǎn)單的會(huì)超時(shí),所以得用來做。算的方法是比如給的例子,現(xiàn)在分成了左右兩部分,拿兩個(gè)指針和。
493. Reverse Pairs
題目鏈接:
https://leetcode.com/problems...
和Count of Smaller Numbers After Self還有count of range sum是一類題,解法都差不多。BST可以做,但是這道題如果輸入是有序的,簡(jiǎn)單的bst會(huì)超時(shí),所以得用AVL來做。
然后就是binary index tree的做法,計(jì)算大于nums[j]2的時(shí)候就是拿全部的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 Mapmap = 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的做法,同樣是每次要統(tǒng)計(jì)左邊有多少結(jié)果是 > 2 * nums[j]的,每次sort完之后先算有多少pairs再merge。算pairs的方法是:
比如給的例子,現(xiàn)在分成了左右兩部分[1, 1, 2], [3, 3],拿兩個(gè)指針i和j。
if nums[i]/2.0 > nums[j],表示所有小與等于nums[j]的值都滿足這個(gè)條件,一直增大到不滿足條件的,最后j - (mid+1)就是全部滿足該條件且包含nums[i]的pair數(shù)目
else, 表示nums[i]小了,需要i++
loop的invariant用包含nums[j]的也行:
ifnums[i]/2.0 > nums[j]表示所有大于等于nums[i]的都滿足條件,res += mid - i + 1,同時(shí)j++
else表示i小了,所以i++
每次重新開一個(gè)aux就超時(shí)了,所以把a(bǔ)ux當(dāng)全局變量,開一次
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++]; } } }
文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/66698.html
摘要:容易出的兩個(gè)地方以為例。這兩個(gè)互為的在尾部加上也就是在頭部加上所以后部分不能為空,否則就和頭部為空的情況重復(fù)了。空間復(fù)雜度因?yàn)橛昧祟~外的來儲(chǔ)存,需要空間。時(shí)間復(fù)雜度每個(gè)分為兩個(gè)部分,調(diào)用前后兩部分總長(zhǎng)度為所以每次調(diào)用為一共次。 Given a list of unique words, find all pairs of distinct indices (i, j) in the g...
摘要:暴力解法就是時(shí)靈時(shí)不靈,兩次一次。希望看到的大神能夠分享優(yōu)質(zhì)的解法謝謝大家 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, ...
摘要:注意這里,只要走到第位 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...
摘要:三指針法復(fù)雜度時(shí)間空間思路基本的操作鏈表,見注釋。注意使用頭節(jié)點(diǎn)方便操作頭節(jié)點(diǎn)。翻轉(zhuǎn)后,開頭節(jié)點(diǎn)就成了最后一個(gè)節(jié)點(diǎn)。 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 ...
摘要:部分是回文的,在里面找是否有的。這里的范圍是,最小是,因?yàn)橐WC是兩個(gè)單詞,最大是,這時(shí)候要找出另一個(gè)和他相反的串。判斷為回文,可以直接暴力,每個(gè)都判斷一次。兩個(gè)方向都找一遍就可能出現(xiàn)重復(fù)的情況,注意避免重復(fù)。例如,結(jié)果應(yīng)該是。 Palindrome Pairs 鏈接:https://leetcode.com/problems... 這道題沒想出來思路,參考了這個(gè)博客的內(nèi)容:http:...
閱讀 1949·2023-04-26 01:59
閱讀 3264·2021-10-11 11:07
閱讀 3295·2021-09-22 15:43
閱讀 3374·2021-09-02 15:21
閱讀 2549·2021-09-01 10:49
閱讀 901·2019-08-29 15:15
閱讀 3089·2019-08-29 13:59
閱讀 2829·2019-08-26 13:36