Leetcode #315: 計算右側小于目前元素的個數

• 題目
• • 題幹
  • 示例
• 題解
• • 方法一：蠻力法。
  • • Python
    • C++
  • 方法二：使用容器。
  • • Python
    • C++
  • 方法三: 建構二叉搜尋樹。
  • • C++

題目

題幹

該問題計算右側小于目前元素的個數 題面：

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].

給定一個整數數組 nums，按要求傳回一個新數組 counts。數組 counts 有該性質：counts[i] 的值是 nums[i] 右側小于 nums[i] 的元素的數量。

示例

輸入：nums = [5,2,6,1]

輸出：[2,1,1,0]

解釋：

5 的右側有 2 個更小的元素 (2 和 1)

2 的右側僅有 1 個更小的元素 (1)

6 的右側有 1 個更小的元素 (1)

1 的右側有 0 個更小的元素

題解

方法一：蠻力法。

時間複雜度O(n2)，額外的空間複雜度O(n)

Python

class Solution1:
    def __init__(self, nums) -> None:
        self.nums = nums

    def countSmaller(self):
        nums_size = len(self.nums)
        result = [0] * nums_size
        for i in range(nums_size):
            for j in range(i+1, nums_size):
                if self.nums[i] > self.nums[j]:
                    result[i] = result[i] + 1
        return result
           

C++

using namespace std;
#include <iostream>
#include <vector>

class Solution1 {
public:
  vector<int> countSmaller(vector<int>& nums) {
    int numsSize = nums.size();
    vector<int> result(numsSize, 0);//用于儲存nums[i]右邊比它小的個數
    for (int i = 0; i < numsSize; ++i){
            //尋找[i + 1, numsSize - 1]中小于nums[i]的元素個數
      for (int j = i + 1; j < numsSize; ++j){
        if (nums[i] > nums[j]){
          result[i] += 1;
        }
      }
    }
    return result;
  }
};
           

方法二：使用容器。

map（預設是按照key從小到大進行排序）進行标記。時間複雜度O(nlog2n)，額外的空間複雜度O(n)

Python

class Solution2:
    def __init__(self, nums) -> None:
        self.nums = nums

    def countSmaller(self):
        nums_size = len(self.nums)
        leftNumCntMap = {}
        result = [0] * nums_size
        for i in range(nums_size-1,-1,-1):
            for k,v in sorted(leftNumCntMap.items()):
                if k >= self.nums[i]:
                    break
                result[i] += v
            leftNumCntMap[self.nums[i]] = leftNumCntMap.setdefault(self.nums[i], 0) + 1

        return result
           

C++

using namespace std;
#include <iostream>
#include <vector>
#include <map>

class Solution2 {
public:
  vector<int> countSmaller(vector<int>& nums) {
    int numsSize = nums.size();
    map<int, int> leftNumCntMap;//用于标記nums[i]左邊各個元素出現的次數
    vector<int> result(numsSize, 0);//用于儲存nums[i]右邊比它小的個數
    for (int i = numsSize - 1; i >= 0; --i){//從後往前進行掃描
      //在map中尋找比nums[i]小的個數
      for (auto &pair : leftNumCntMap){
        if (pair.first >= nums[i]){
          break;
        }
        result[i] += pair.second;
      }
      //将nums[i]标記出現次數增加
      leftNumCntMap[nums[i]] += 1;
    }
    return result;
  }
};
           

方法三: 建構二叉搜尋樹。

利用二叉搜尋樹的特性，計算比目前節點小的個數。時間複雜度O(nlog2n)，額外的空間複雜度O(n) 。

二叉搜尋樹的特性：中序周遊序列嚴格遞增。

C++

using namespace std;
#include <iostream>
#include <vector>

class Solution3 {
private:
    struct BSTNode{
        int val;
        int leftCount;//标記目前節點左端的節點數（記不比val大的個數）
        BSTNode *left;
        BSTNode *right;
        BSTNode(int x):val(x),left(nullptr),right(nullptr),leftCount(0){}
    };

public:
    //将insert_node插入node二叉搜尋樹中，并将node中節點值比insert_node小的個數放入count_small中
    void BST_insert(BSTNode *treeRoot, BSTNode *insert_node, int &count_small){
        if(insert_node->val <= treeRoot->val){//需要插入treeRoot的左端
            treeRoot->leftCount += 1;//左端節點自增
            if(treeRoot->left){
                BST_insert(treeRoot->left, insert_node, count_small);
            }else{
                treeRoot->left=insert_node;
            }
        }
        else{//插入treeRoot的右端
            count_small += treeRoot->leftCount + 1;//最小值為目前節點右端節點個數 + 1（目前根節點）
            if(treeRoot->right){
                BST_insert(treeRoot->right, insert_node, count_small);
            }else{
                treeRoot->right=insert_node;
            }
        }
    }

    vector<int> countSmaller(vector<int>& nums) {
        //建立二叉查找樹節點池
        vector<BSTNode*> node_vec;
        for (auto num : nums){
            node_vec.push_back(new BSTNode(num));
        }
        int node_vecSize = node_vec.size();
        vector<int> result(node_vecSize, 0);
        //将第n - 2到0第個節點插入到以第n - 1節點為根節點的二叉排序樹中
        //插入過程中計算每個節點的countSmaller
        for(int i = node_vecSize - 2; i >= 0; --i){
            BST_insert(node_vec[node_vecSize - 1], node_vec[i], result[i]);
        }
        return result;
    }
};