[Leetcode]315. Count of Smaller Numbers After Self(C++)

题目描述

题目链接：315. Count of Smaller Numbers After Self

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

例子

例子 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]

Follow Up

Note

Constraints

1 <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

解题思路

这道题有几种思路，分别如下：

二分查找树

最初的思路是：我们知道在二分查找树当中，一个节点的左子树中所有节点都该根节点小，假如我们将左字数节点数量作为节点的值存起来，我们就可以在常数时间内获得比该节点小的元素的个数。完整过程如下：

定义一个树节点，节点值包括元素值val，符合该值的元素个数count，以及其左子树的节点个数left_count （同一个节点如果有多个对应数组的元素需要每个都考虑）
从后往前遍历数组，现将数组最后一个值构建为根节点（num, 1, 0）
继续遍历数组，对每一个数组操作如下：
初始化当前节点为根节点，右侧比他小的元素 result 数量为 0
判断数组值和当前节点值的大小关系：
- 如果值相等，合并进该节点（curr->count++），同时将该节点的左子树节点个数加入结果中：result += curr->left_count
- 如果数值大于节点值，继续往右判断：
  - 我们可以知道当前节点的元素个数以及其左子树节点的个数都比当前数组元素小，所以result += (curr->count + curr->left_count)
  - 假如当前节点右子树为空，即找到插入位置，新建右子树并退出循环
  - 否则当前节点更新为右子树根节点，继续循环
- 如果数组小于节点值，往左判断：
  - 更新当前的节点的左子树节点个数值 curr->left_count++
  - 假如当前节点左子树为空，即找到插入位置，新建右子树并退出循环
  - 否则当前节点更新为左子树根节点，继续循环
退出循环中将结果添加进返回数组中，继续遍历下一个数组值
翻转返回数组，然后返回

代码如下：

#include <algorithm>
#include <tuple>
#include <vector>

class Solution {
public:
    struct TreeNode {
        // val, count of this value, count of nodes in left tree
        std::tuple<int, int, int> val;
        TreeNode* left = nullptr;
        TreeNode* right = nullptr;

        TreeNode() {}
        TreeNode(const std::tuple<int, int, int>& val_) : val(val_) {}
    };

    std::vector<int> countSmaller(std::vector<int>& nums) {
        TreeNode* head = new TreeNode({nums.back(), 1, 0});
        std::vector<int> result{0};

        for (size_t i = nums.size() - 2; i >= 0; i++) {
            int num = nums[i];
            int count = 0;
            TreeNode* curr = head;
            while (true) {
                int curr_val = std::get<0>(curr->val);
                if (curr_val == num) {
                    std::get<1>(curr->val)++;
                    count += std::get<2>(curr->val);

                    break;
                } else if (curr_val < num) {
                    count += std::get<2>(curr->val);
                    count += std::get<1>(curr->val);
                    if (!curr->right) {
                        curr->right = new TreeNode({num, 1, 0});
                        break;
                    } else {
                        curr = curr->right;
                    }
                } else {
                    std::get<2>(curr->val)++;
                    if (!curr->left) {
                        curr->left = new TreeNode({num, 1, 0});
                        break;
                    } else {
                        curr = curr->left;
                    }
                }
            }
            result.push_back(count);
        }

        std::reverse(result.begin(), result.end());

        return result;
    }
};

时间复杂度: O(nlog n) -> O(n^2) ：数组完全逆序时，时间复杂度为 O(n^2)
空间复杂度: O(count(unique(nums)))

GitHub 代码同步地址： 315.CountOfSmallerNumbersAfterSelf.cpp

其他题目： GitHub: Leetcode-C++-Solution 博客： Leetcode-Solutions