資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中自右向左小於當前元素的個數
假設我們有一個數組 nums，我們需要找到另一個名為 count 的陣列，在這個 count 陣列中，count[i] 儲存 nums[i] 右側較小元素的數量。
因此，如果輸入類似於：[5,2,7,1]，則結果將為 [2,1,1,0]。
為了解決這個問題，我們將遵循以下步驟 -
定義一個名為 update() 的方法，它將接收索引、陣列 bit 和 n 作為引數。
當 index <= n 時，執行 -
增加 bit[index] 的值。
index = index + (index) AND ( - index)
定義一個名為 query() 的陣列，它將接收索引和 bits 陣列作為引數。
ans := 0
當 index > 0 時，執行 -
ans = ans + bit[index]
index = index – (index AND - index)
返回 ans
從主方法中，執行以下操作 -
n := nums 的大小。
定義一個大小為 n 的陣列 res。
如果 (n 不為零) 為假，則返回 res。
maxx := 0，minn = nums [0]
初始化 i := 1，當 i < n 時，將 i 增加 1，執行 -
minn := nums[i] 和 minn 中的最小值。
初始化 i := 0，當 i < n 時，將 i 增加 1，執行 -
nums[i] := nums[i] - minn + 1
maxx := nums[i] 和 maxx 中的最大值。
定義一個大小為 maxx + 1 的陣列 bit。
初始化 i := n - 1，當 i >= 0 時，將 i 減小 1，執行 -
num = nums[i] – 1
x := 呼叫函式 query(num,bit)
res[i] := x
呼叫函式 update(num + 1, bit, maxx)
返回 res
示例
讓我們看看以下實現以獲得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
void update(int index,vector <int>& bit, int n){
while(index<=n){
bit[index]++;
index += (index)&(-index);
}
}
int query(int index, vector <int> bit){
int ans = 0;
while(index>0){
ans+=bit[index];
index -= index&(-index);
}
return ans;
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector <int> res(n);
if(!n)return res;
int maxx = 0;
int minn = nums[0];
for(int i =1;i<n;i++)minn = min(nums[i],minn);
for(int i =0;i<n;i++){
nums[i] = nums[i]-minn+1;
maxx = max(nums[i],maxx);
}
vector <int> bit(maxx+1);
for(int i =n-1;i>=0;i--){
int num = nums[i]-1;
int x = query(num,bit);
res[i] = x;
update(num+1,bit,maxx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {5,2,7,1};
print_vector(ob.countSmaller(v));
}輸入
[5,2,7,1]
輸出
[2, 1, 1, 0, ]
301 次檢視
