Skip to content

Instantly share code, notes, and snippets.

@rfaisal
Last active September 18, 2022 19:34
Show Gist options
  • Save rfaisal/ec0577af523be984e2239ad3c3a25945 to your computer and use it in GitHub Desktop.
Save rfaisal/ec0577af523be984e2239ad3c3a25945 to your computer and use it in GitHub Desktop.
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
idx = [0 for x in range(len(nums))]
for i in range(len(nums)):
idx[i] = (nums[i], i)
# print(idx)
result = [0 for x in range(len(nums))]
p = self.mergeSort(idx, result)
print(p)
#print(result)
return result
def mergeSort(self, nums, result):
if len(nums) <= 1:
return nums
mid = (int)(len(nums)/2)
left = nums[0:mid]
right = nums[mid:]
left = self.mergeSort(left, result)
right = self.mergeSort(right, result)
return self.merge(left, right, result, 0)
def merge(self, left, right, result, count):
if len(left) == 0:
return list(right) # return right (cloned)
if len(right) == 0:
for x in left:
result[x[1]] += count
return list(left) # return left (cloned)
if left[0][0] > right[0][0]:
return [right[0]] + self.merge(left,right[1:],result, count + 1)
else:
result[left[0][1]] += count
return [left[0]] + self.merge(left[1:],right,result, count)
def merge1(self, left, right, result):
merged = []
i = 0
j = 0
count = 0
while i<len(left) and j<len(right):
if left[i][0] > right[j][0]:
count += 1 # items from right moves over
merged.append(right[j])
j += 1
else:
result[left[i][1]] += count # no more items smaller / moves over for i
merged.append(left[i])
i += 1
# if any left is reamaining
while i<len(left):
result[left[i][1]] += count
merged.append(left[i])
i += 1
while j<len(right):
merged.append(right[j])
j += 1
return merged
class Solution(object):
def countSmaller(self, nums):
"""
:type nums: List[int]
:rtype: List[int]
"""
idx = [0 for x in range(len(nums))]
for i in range(len(nums)):
idx[i] = (nums[i], i)
# print(idx)
result = [0 for x in range(len(nums))]
p = self.mergeSort(idx, result)
print(p)
#print(result)
return result
def mergeSort(self, nums, result):
if len(nums) <= 1:
return nums
mid = (int)(len(nums)/2)
left = nums[0:mid]
right = nums[mid:]
left = self.mergeSort(left, result)
right = self.mergeSort(right, result)
return self.merge(left, right, result)
def merge(self, left, right, result):
merged = []
i = 0
j = 0
count = 0
while i<len(left) and j<len(right):
if left[i][0] > right[j][0]:
count += 1 # items from right moves over
merged.append(right[j])
j += 1
else:
result[left[i][1]] += count # no more items smaller / moves over for i
merged.append(left[i])
i += 1
# if any left is reamaining
while i<len(left):
result[left[i][1]] += count
merged.append(left[i])
i += 1
while j<len(right):
merged.append(right[j])
j += 1
return merged
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment