LeetCode — Подсчет меньших чисел после себя

Постановка задачи

Получив массив целых чисел nums, верните целочисленный массив counts, где counts[i] — это количество меньших элементов справа от nums[i].

Постановка задачи взята с: https://leetcode.com/problems/count-of-smaller-numbers-after-self

Пример 1:

Input: nums = [5, 2, 6, 1]
Output: [2, 1, 1, 0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Пример 2:

Input: nums = [-1]
Output: [0]

Пример 3:

Input: nums = [-1, -1]
Output: [0, 0]

Ограничения:

- 1 <= nums.length <= 10^5
- -10^4 <= nums[i] <= 10^4

Объяснение

Решение грубой силы

Наивный подход — использовать вложенные циклы. Внешний цикл выбирает все элементы слева направо. Внутренний цикл выполняет итерацию по всем элементам справа от выбранного элемента и обновляет количество элементов меньше числа.

Фрагмент C++ этого подхода выглядит следующим образом:

vector<int> countSmaller(vector<int>& nums) {
    int i, j;
    vector<int> ans;
    int n = nums.size();

    for (i = 0; i < n; i++)
        ans[i] = 0;

    for (i = 0; i < n; i++) {
        for (j = i + 1; j < n; j++) {
            if (nums[j] < nums[i])
                ans[i]++;
        }
    }
}

Временная сложность этого подхода составляет O(n²). Сложность пространства составляет O(n).

АВЛ-дерево

В этом подходе мы используем самобалансирующееся двоичное дерево поиска, дерево AVL.

Мы перебираем массив справа налево и вставляем элементы один за другим в дерево AVL. При вставке нового ключа в дерево AVL мы сравниваем элемент с корневым значением дерева. Если элемент больше корня, то все узлы в левом поддереве меньше элемента. К вставляемому элементу добавляем размер левого поддерева. Мы рекурсивно используем один и тот же подход для всех узлов.

Фрагмент C++ этого подхода выглядит следующим образом:

struct node {
    int key;
    struct node* left;
    struct node* right;
    int height;
    int size;
};

int height(struct node* node) {
    return node != NULL ? node->height : 0;
}

int size(struct node* node) {
    return node != NULL ? node->size : 0;
}

int max(int a, int b) { return (a > b) ? a : b; }

struct node* newNode(int key) {
    struct node* node = (struct node*)malloc(sizeof(struct node));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1;
    node->size = 1;

    return node;
}

struct node* rightRotate(struct node* y) {
    struct node* leftTree = y->left;
    struct node* T2 = leftTree->right;

    leftTree->right = y;
    y->left = T2;

    y->height = max(height(y->left), height(y->right)) + 1;
    leftTree->height = max(height(leftTree->left), height(leftTree->right)) + 1;

    y->size = size(y->left) + size(y->right) + 1;
    leftTree->size = size(leftTree->left) + size(leftTree->right) + 1;

    return x;
}

struct node* leftRotate(struct node* x) {
    struct node* y = x->right;
    struct node* T2 = y->left;

    y->left = x;
    x->right = T2;

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    x->size = size(x->left) + size(x->right) + 1;
    y->size = size(y->left) + size(y->right) + 1;

    return y;
}

int getBalance(struct node* node) {
    return node != NULL ? height(node->left) - height(node->right) : 0;
}

struct node* insert(struct node* node, int key, int* count) {
    if (node == NULL)
        return (newNode(key));

    if (key < node->key)
        node->left = insert(node->left, key, count);
    else {
        node->right = insert(node->right, key, count);
        *count = *count + size(node->left) + 1;
    }

    node->height = max(height(node->left), height(node->right)) + 1;
    node->size = size(node->left) + size(node->right) + 1;

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

    if (balance > 1 && key > node->left->key) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    if (balance < -1 && key < node->right->key) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

void constructLower(int nums[]) {
    int i, j;
    int n = nums.size();
    struct node* root = NULL;

    for (i = 0; i < n; i++)
        ans[i] = 0;

    for (i = n - 1; i >= 0; i--) {
        root = insert(root, nums[i], &ans[i]);
    }
}

Временная сложность этого подхода составляет O(n * log(n)). Сложность пространства составляет O(n).

Сортировка слиянием

Идея состоит в том, чтобы использовать алгоритм MergeSort. При обратном слиянии массива, как и при сортировке слиянием, мы сортируем элементы массива в порядке убывания и отслеживаем меньшие элементы.

Мы знаем, как работает сортировка слиянием, давайте сначала проверим алгоритм.

Алгоритм

//countSmaller(nums)
- initialize vector pair v
  set n = nums.size
  set ans = vector<int> ans(n, 0)

- loop for i = 0; i < n; i++
  // push the element and the index
  - v.push_back({ nums[i], i })
- for end

- mergesort(v, ans, 0, n - 1)

- return ans

// mergesort(v, ans, i, j)
- if i < j
  - set mid = (i + j) / 2

  //recursively call left half of the array
  - mergesort(v, ans, i, mid)

  //recursively call right half of the array
  - mergesort(v, ans, mid + 1, j)

  // merge the array and sort the elements
  - merge(v, ans, i, mid, j)
- if end

// merge(v, ans, l, mid, h)
- initialize vector pair temp
  set i = l
  set j = mid + 1

- loop while i < mid + 1 && j <= h
  - if v[i].first > v[j].first
    // add up all the elements that are less than this element
    // and these elements are present in the 2nd half of the array
    - set ans[v[i].second] += (h - j + 1)

    - temp.push_back(v[i])

    - increment i, i++
  - else
    - temp.push_back(v[j])

    - increment j, j++
  - if end
- while end

- loop while i <= mid
  - temp.push_back(v[i])
  - i++
- while end

- loop while j <= h
  - temp.push_back(v[j])
  - j++
- while end

- loop for k = 0, i = l; i <= h; i++, k++
  - v[i] = temp[k]
- for end

Временная сложность этого подхода составляет O(n * log(n)). Сложность пространства составляет O(n).

Давайте проверим наш алгоритм на C++, Golang и JavaScript.

С++ решение

class Solution {
public:
    void merge(vector<pair<int, int>> &v, vector<int> &ans, int l, int mid, int h) {
        vector<pair<int, int>> temp;
        int i = l;
        int j = mid + 1;

        while (i < mid + 1 && j <= h) {
            if (v[i].first > v[j].first) {
                ans[v[i].second] += (h - j + 1);
                temp.push_back(v[i]);
                i++;
            } else {
                temp.push_back(v[j]);
                j++;
            }
        }

        while (i <= mid)
            temp.push_back(v[i++]);

        while (j <= h)
            temp.push_back(v[j++]);

        for (int k = 0, i = l; i <= h; i++, k++)
            v[i] = temp[k];
    }

    void mergesort(vector<pair<int, int>> &v, vector<int> &ans, int i, int j) {
        int mid;

        if(i < j) {
            mid = (i + j) / 2;

            mergesort(v, ans, i, mid);

            mergesort(v, ans, mid + 1, j);

            merge(v, ans, i, mid, j);
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<pair<int, int>> v;
        int n = nums.size();
        vector<int> ans(n, 0);

        for (int i = 0; i < n; i++) {
            v.push_back({nums[i], i});
        }

        mergesort(v, ans, 0, n - 1);

        return ans;
    }
};

Голанг решение

type Pair struct {
 Val   int
 Index int
}

func merge(v []Pair, ans []int, l, mid, h int) {
 temp := make([]Pair, h - l +1)
 i, j, k := l, mid + 1, 0

    for i <= mid && j <= h {
  if v[i].Val > v[j].Val {
            ans[v[i].Index] += h - j + 1
   temp[k] = v[i]
   i++

  } else {
   temp[k] = v[j]
   j++
  }

  k++
 }

 for i <= mid {
  temp[k] = v[i]
  i++
  k++
 }
 for j <= h {
  temp[k] = v[j]
  j++
  k++
 }

 for i := l; i <= h; i++ {
  v[i] = temp[i - l]
 }
}

func mergeSort(v []Pair, ans []int, i, j int) {
 if i < j {
  mid := (i + j)/2
  mergeSort(v, ans, i, mid)
  mergeSort(v, ans, mid + 1, j)
  merge(v, ans, i, mid, j)
 }
}

func countSmaller(nums []int) []int {
 n := len(nums)
 ans := make([]int, n)
 v := make([]Pair, n)
 for index, value := range nums {
  v[index] = Pair{value, index}
 }

 mergeSort(v, ans, 0, n - 1)

 return ans
}

JavaScript-решение

var merge = function(v, ans, l, mid, h) {
    let temp = [];
    let i = l, j = mid + 1;

    while(i < mid + 1 && j <= h) {
        if(j < v.length && v[i][0] > v[j][0]) {
            ans[v[i][1]] += (h - j + 1);
            temp.push(v[i]);
            i++;
        } else {
            temp.push(v[j]);
            j++;
        }
    }

    while (i <= mid)
        temp.push(v[i++]);

    while (j <= h)
        temp.push(v[j++]);

    for (let k = 0, i = l; i <= h; i++, k++)
        v[i] = temp[k];
}

var mergesort = function(v, ans, i, j) {
    let mid;

    if(i < j) {
        mid = Math.round((i + j) / 2)-1;

        mergesort(v, ans, i, mid);

        mergesort(v, ans, mid + 1, j);

        merge(v, ans, i, mid, j);
    }
}

var countSmaller = function(nums) {
    let v = [];
    let n = nums.length;
    let ans = new Array(n);

    for(let i = 0; i < n; i++) {
        let x = [nums[i], i];
        v.push(x);
    }

    for(let i = 0; i < n; i++) {
        ans[i] = 0;
    }

    mergesort(v, ans, 0, n - 1);

    return ans;
};

Давайте проверим наш алгоритм на нескольких примерах, чтобы увидеть, как работает решение.

Input: nums = [5, 2, 6, 1]

// countSmaller
Step 1: vector<pair<int, int>> v

        int n = nums.size()
              = 4

        vector<int> ans(n, 0)

Step 2: loop for int i = 0; i < n; i++
            v.push_back({nums[i], i});
        for end

        v will be [[5, 0], [2, 1], [6, 2], [1, 3]]

Step 3: mergesort(v, ans, 0, n - 1)
        mergesort(v, ans, 0, 3)

// mergesort(v, ans, 0, 3)
Step 4: if i < j
         0 < 3
         true

         mid = i + j / 2
             = 0 + 3 / 2
             = 1

         mergesort(v, ans, i, mid)
         mergesort(v, ans, 0, 1)

// mergesort(v, ans, 0, 1)
Step 5: if i < j
         0 < 1
         true

         mid = i + j / 2
             = 0 + 1 / 2
             = 0

         mergesort(v, ans, i, mid)
         mergesort(v, ans, 0, 0)

// mergesort(v, ans, 0, 0)
Step 6: if i < j
         0 < 1
         false

         we rollback to step 5

// mergesort(v, ans, 0, 1)
Step 7: if i < j
         0 < 1
         true

         mid = i + j / 2
             = 0 + 1 / 2
             = 0

         mergesort(v, ans, i, mid)
         mergesort(v, ans, 0, 0)    // evaluated in Step 6

         mergesort(v, ans, mid + 1, j)
         mergesort(v, ans, 0 + 1, 3)
         mergesort(v, ans, 1, 3)

// mergesort(v, ans, 1, 3)
Step 8: if i < j
         1 < 3
         true

         mid = i + j / 2
             = 1 + 3 / 2
             = 2

         mergesort(v, ans, i, mid)
         mergesort(v, ans, 1, 2)

         This recursion occurs till we get each element as
         [5], [2], [6], [1]

         We then reach a step where we first merge 6 and 1 and call
         merge(v, ans, i, mid, j)
         merge(v, ans, 2, 2, 3)

// merge(v, ans, 2, 2, 3)
Step 9: vector<pair<int, int>> temp
        int i = l
              = 2
        int j = mid + 1
              = 2 + 1
              = 3

        loop while i < mid + 1 && j <= h
          2 < 2 + 1 && 3 <= 3
          true

          if v[i].first > v[j].first
             v[2].first > v[3].first
             6 > 1
             true

             ans[v[i].second] = ans[v[i].second] + (h - j + 1)
             ans[v[2].second] = ans[v[2].second] + 3 - 3 + 1
                              = 0 + 1
                              = 1
             ans = [0, 0, 1, 0]

             temp.push_back(v[i])
             temp = [[6, 2]]

             i++
             i = 3

          if end

        loop while i < mid + 1 && j <= h
          3 < 2 + 1 && 3 <= 3
          false

        loop while i <= mid
          3 <= 2
          false

        loop while j <= h
          3 <= 3
          true

          temp.push_back(v[j])
          temp.push_back(v[3])
          temp = [[6, 2], [1, 3]]

          j++
          j = 4

        loop while j <= h
          4 <= 3
          false

        loop for int k = 0, i = l; i <= h;
          k = 0
          i = 2

          i <= h
          2 <= 3

          v[i] = temp[k]
          v[2] = temp[0]
               = [6, 2]

          i++
          i = 3

          k++
          k = 1

        loop for i <= h
          3 <= 3
          true

          k = 1
          i = 3

          v[i] = temp[k]
          v[3] = temp[1]
               = [1, 3]

          i++
          i = 4

          k++
          k = 2

        loop for i <= h
          4 <= 3
          false

        We backtrack to step where we merge 5 and 2.

        We then backtrack to step where we merge [5, 2] and [6, 1]

We keep updating the ans array and get the final result as [2, 1, 1, 0].

Первоначально опубликовано на https://alkeshghorpade.me.

👋 Если вы считаете это полезным, пожалуйста, несколько раз нажмите кнопку аплодисментов 👏 ниже, чтобы выразить свою поддержку автору 👇

🚀Присоединяйтесь к сообществу разработчиков FAUN и получайте похожие истории в свой почтовый ящик каждую неделю