Подсчитайте больше элементов справа от себя

Question

Этот вопрос, приведенный ниже, сводит меня с ума. Если кто-то может помочь, пожалуйста.

"При заданном массиве Num из 'n' элементов возвращается массив A длиной 'n', в котором A [i] содержит число элементов, превышающее Num [i] справа от него в исходном массиве"

Я видел SO-ответ здесь , но он содержит решение O (n ^ 2). Мне нужно решение O (nlogn) .

У меня есть решение для "Считать меньшие элементы слева от себя". Но его изменение не дало мне необходимого решения (см. Код ниже).

Любая помощь приветствуется:)

class BinarySearchTreeNode(object):
   def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.count = 1
    self.leftTreeSize = 0

class BinarySearchTree(object):
   def __init__(self):
    self.root = None

   def insert(self, val, root):
    if not root:
        self.root = BinarySearchTreeNode(val)
        return 0

    if val == root.val:
        root.count += 1
        return root.leftTreeSize

    if val < root.val:
        root.leftTreeSize += 1

        if not root.left:
            root.left = BinarySearchTreeNode(val)
            return 0
        return self.insert(val, root.left)

    if not root.right:
        root.right = BinarySearchTreeNode(val)
        return root.count + root.leftTreeSize

    return root.count + root.leftTreeSize + self.insert(val, root.right)

class Solution(object):
  def countSmaller(self, nums):

    tree = BinarySearchTree()
    return [
        tree.insert(nums[i], tree.root)
        for i in range(len(nums) - 1, -1, -1)
    ][::-1]

print(Solution().countSmaller(nums = [1, 4, 2, 7]))

Пример:

Заданный массив [10, 7, 2, 6, 5]

, тогда меньший по размеру справа массив [4, 3, 0, 1, 0]

Массив слева направо равен [0, 1, 2, 2, 3]

Надеюсь, это поможет ...

Answer 1

class Node(object):
def __init__(self, val):
    self.val = val
    self.left = None
    self.right = None
    self.count = 1
    self.rightTreeSize = 0
    self.leftTreeSize = 0

class BinarySearchTree(object):
def __init__(self):
    self.root = None

def insert(self, val, root):
    if not root:
        self.root = Node(val)
        return 0

    if val == root.val:
        root.count += 1
        return root.rightTreeSize

    if val > root.val:
        root.rightTreeSize += 1

        if not root.right:
            root.right = Node(val)
            return 0
        return self.insert(val, root.right)

    if not root.left:
        root.left = Node(val)
        return root.count + root.rightTreeSize

    return root.count + root.rightTreeSize + self.insert(val, root.left)


class BinarySearchTree1(object):
def __init__(self):
    self.root = None

def insert(self, val, root):
    if not root:
        self.root = Node(val)
        return 0

    if val == root.val:
        root.count += 1
        return root.leftTreeSize

    if val < root.val:
        root.leftTreeSize += 1

        if not root.left:
            root.left = Node(val)
            return 0
        return self.insert(val, root.left)

    if not root.right:
        root.right = Node(val)
        return root.count + root.leftTreeSize

    return root.count + root.leftTreeSize + self.insert(val, root.right)



class Solution(object):
def countGreater(self):
    nums = [10, 7, 2, 6, 5]
    tree = BinarySearchTree()
    print([tree.insert(nums[i], tree.root) for i in range(0, len(nums))])

def countSmaller(self):
    nums = [10, 7, 2, 6, 5]        
    tree1 = BinarySearchTree1()
    print([tree1.insert(nums[i], tree1.root) for i in range(len(nums) - 1, -1, -1)][::-1])


Solution().countSmaller()
Solution().countGreater()

Извините за проблемы с отступами, не удалось настроить все строки в редакторе уценки.

Приведенный выше код возвращает "Количество меньших элементов справа от себя" и "Количество больших элементов слева от себя"

Answer 2

Ну, я не знаю, ищите ли вы это решение, так как я предполагаю, что вы хотели, чтобы я исправил ваш код, но можно подойти к этому так:

число = [10, 7, 2, 6, 5]

mergeSort (num) или heapSort (num). Я не знаю, есть ли в Python встроенные, или вам нужно внедрить себя. но mergeSort / heapSort это имеет худшую сложность O (nlog (n).

sortedNum = [2,5,6,7,10]

answer = []

for every number in Num: 
    binarySearch number in sortedNum and return its position
    answer.appened(position)
    delete item from sortedNum at position.

Сам цикл for имеет сложность O (n), а двоичный поиск внутри цикла имеет сложность log (n). Таким образом, эта функция имеет сложность O (n log (n)), поскольку добавление и удаление занимает O (1)

Это означает, что сортировка + псевдокодированная функция имеет общую сложность O (2nlog (n)) = O (nlog (n)).

Редактировать: Так как я ошибся, и вы хотели посчитать больше элементов слева от себя.

Здесь сортировка не требуется!

число = [10,7,2,6,5]

sortedNum = []

answer = []

for every number in Num:
    position = binarySearch number in sortedNum to which numbers its inbetween. 
    insert number into that position into sortedNum
    answer.append(len(num)-position)