-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathNumber of Pairs Satisfying Inequality
62 lines (56 loc) · 1.58 KB
/
Number of Pairs Satisfying Inequality
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
link- https://leetcode.com/problems/number-of-pairs-satisfying-inequality/
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild=None
class Solution:
def checkCount(self,start,mid,end,d):
global counti
global arr
l=start
r=mid+1
while l<=mid and r<=end:
if arr[l]<=arr[r]+d:
counti+=end-r+1
l+=1
else:
r+=1
# arr=arr[:start]+sorted(arr[start:end+1])+arr[end+1:]
l=start
r=mid+1
tem=[]
while l<=mid and r<=end:
if arr[l]<=arr[r]:
tem.append(arr[l])
l+=1
else:
tem.append(arr[r])
r+=1
while l<=mid:
tem.append(arr[l])
l+=1
while r<=end:
tem.append(arr[r])
r+=1
l=start
for i in range(len(tem)):
arr[l+i]=tem[i]
def mergeSort(self,start,end,d):
global arr
if start==end:
return
mid=(start+end)//2
self.mergeSort(start,mid,d)
self.mergeSort(mid+1,end,d)
self.checkCount(start,mid,end,d)
def numberOfPairs(self, nums1: List[int], nums2: List[int], diff: int) -> int:
n=len(nums1)
global arr
arr=[0]*n
for i in range(n):
arr[i]=nums1[i]-nums2[i]
global counti
counti=0
self.mergeSort(0,n-1,diff)
return counti