題目描述
Imagine you are reading in a stream of integers. Periodically, you wish to be able to look up the rank of a number x (the number of values less than or equal to x). lmplement the data structures and algorithms to support these operations. That is, implement the method track (int x), which is called when each number is generated, and the method getRankOfNumber(int x), which returns the number of values less than or equal to x.
面試題 10.10. Rank from Stream LCCI 中等之困難
題解
暴力普通陣列
思路
假設整數流中的整數在0~50000之間，那么我們可以預先建立一個大小為50001的int[]陣列，來記錄每個整數出現的次數，查詢比n小的個數時，只需從0遍歷到n即可，
代碼
class StreamRank {
int[] nums;
public StreamRank() {
nums = new int[50001];
}
public void track(int x) {
nums[x]++;
}
public int getRankOfNumber(int x) {
int ans = 0;
for (int i = 0;i <= x;i++){
ans += nums[i];
}
return ans;
}
}
時間復雜度分析
添加元素只需自增，為\(O(1)\)，查詢時需要遍歷所有比n小的數，時間復雜度為\(O(n)\)，若查詢次數為m，插入次數為n，則時間復雜度為\(O(n+mn)\)，
暴力前綴和陣列
思路
假設同一，將普通陣列改為前綴和陣列，
代碼
class StreamRank {
int[] nums;
public StreamRank() {
nums = new int[50001];
}
public void track(int x) {
for(int i = x;i <= 50000;i++){
nums[i]++;
}
}
public int getRankOfNumber(int x) {
return nums[x];
}
}
時間復雜度分析
和解法一正相反，前綴和陣列插入的時間復雜度是\(O(n)\)，查詢的時間復雜度為\(O(1)\)，若查詢次數為m，插入次數為n，則時間復雜度為\(O(n^2+m)\)，
二叉搜索樹
解法一：每個結點額外存盤左子樹中小于本結點的結點數目以及自身數目之和
class StreamRank {
BSTree bsTree;
public StreamRank() {
bsTree = new BSTree();
}
public void track(int x) {
bsTree.add(x);
}
public int getRankOfNumber(int x) {
return bsTree.query(x);
}
}
class BSTree{
TreeNode root;
public BSTree(){
}
public void add(int x){
if(root == null){
root = new TreeNode(x);
}
else{
TreeNode p = root;
while(true){
if(x == p.val){//樹中已有該值，直接把數量加1
p.num++;
break;
}
else if(x < p.val){
if(p.left == null){
p.left = new TreeNode(x);
p.num++;//若是左子樹，則當前結點num加1
break;
}
p.num++;//若是左子樹，則當前結點num加1
p = p.left;
}
else{
if(p.right == null){
p.right = new TreeNode(x);
break;
}
p = p.right;
}
}
}
}
public int query(int x){
return queryFunc(root, x);
}
private int queryFunc(TreeNode root, int x){
if(root == null){
return 0;
}
if(x == root.val){//恰好命中，回傳該命中結點的num域
return root.num;
}
else if(x < root.val){//遞回在左子樹中查找
return queryFunc(root.left, x);
}
else{//先加上根節點的num域，再遞回在右子樹中查找
return root.num + queryFunc(root.right, x);
}
}
}
class TreeNode{
int val;
int num;//存盤左子樹中小于本結點的個數與本結點數目之和
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
this.num = 1;
}
}
解法二：每個結點額外存盤自身數目以及子結點總數兩個域
class StreamRank {
BSTree bsTree;
public StreamRank() {
bsTree = new BSTree();
}
public void track(int x) {
bsTree.add(x);
}
public int getRankOfNumber(int x) {
return bsTree.query(x);
}
}
class BSTree{
TreeNode root;
public BSTree(){
}
public void add(int x){
if(root == null){
root = new TreeNode(x);
}
else{
TreeNode p = root;
while(true){
if(x == p.val){//等于當前結點，表明樹中已有該值，直接把結點自身數量加1
p.selfNum++;
break;
}
else if(x < p.val){//小于當前結點
if(p.left == null){//若當前結點左子樹為空，則新建結點，并將當前結點子結點數目加1
p.left = new TreeNode(x);
p.childNum++;
break;
}
p.childNum++;//若當前結點左子樹非空，繼續向左尋找，并將當前結點子結點數目加1
p = p.left;
}
else{//大于當前節點
if(p.right == null){//若當前結點右子樹為空，則新建結點，并將當前結點子節點數目加1
p.right = new TreeNode(x);
p.childNum++;
break;
}
p.childNum++;//若當前結點右子樹非空，繼續向右尋找，并將當前結點子節點數目加1
p = p.right;
}
}
}
}
public int query(int x){
return queryFunc(root, x);
}
private int queryFunc(TreeNode root, int x){
if(root == null){
return 0;
}
if(x == root.val){
//查詢結點等于當前結點，那么小于等于查詢結點的數目=該結點的selfNum+左子樹的結點數(即左孩子的selfNum+左孩子的子結點數目)
return root.selfNum + (root.left == null ? 0 : root.left.childNum + root.left.selfNum);
}
else if(x < root.val){
//查詢結點小于當前結點，那么遞回地在左子樹中查詢
return queryFunc(root.left, x);
}
else{
//查詢結點大于當前結點，那么就已經知道，至少根結點和左子樹的所有結點都小于查詢結點
//于是先加上這些已知的結點數目，再遞回地在右子樹中查詢
return root.selfNum + (root.left == null ? 0 : root.left.childNum + root.left.selfNum) + queryFunc(root.right, x);
}
}
}
class TreeNode{
int val;
int selfNum;//結點自身數目
int childNum;//子結點個數
TreeNode left;
TreeNode right;
public TreeNode(int val){
this.val = val;
this.childNum = 0;
this.selfNum = 1;
}
}
復雜度分析
對于二叉搜索樹，平均每次插入和查詢為\(O(logn)\)的時間復雜度，n次插入和查詢則為\(O(nlogn)\)的時間復雜度，
最壞情況下，二叉搜索樹形成一條鏈，時間復雜度接近\(O(n^2)\)，
演算法改進
由于特殊情況下二叉查找樹的退化，本題可以使用改進的二叉查找自平衡樹，如AVL樹、紅黑樹等，
由于AVL樹、紅黑樹的實作代碼比較復雜，這里就不再討論，對于本題，除了樹的具體實作方式不同，他們額外添加的結點資訊都是相同的，
樹狀陣列
思路
限制資料流中的數字最大為50000、最小為0的情況下，使用樹狀陣列可以在O(logn)的時間內快速更新和查詢，
代碼
class StreamRank {
FenwickTree fenwickTree;
public StreamRank() {
fenwickTree = new FenwickTree(50001);
}
public void track(int x) {
fenwickTree.update(x, 1);
}
public int getRankOfNumber(int x) {
return fenwickTree.query(x);
}
}
class FenwickTree{
int[] tree;
int len;
public FenwickTree(int n){
this.tree = new int[n + 1];
this.len = n;
}
public void update(int i, int dest){
i++;//由于0的存在，向右平移一位
while(i <= len){
tree[i] += dest;
i += lowbit(i);
}
}
public int query(int i){
i++;//由于0的存在，向右平移一位
int sum = 0;
while(i > 0){
sum += tree[i];
i -= lowbit(i);
}
return sum;
}
private int lowbit(int x){
return x & (-x);
}
}
復雜度分析：
使用樹狀陣列可以在\(O(logn)\)的時間內快速更新和查詢，n次更新和查詢的時間復雜度為\(O(nlogn)\)，
缺點及改進：
當資料流中的數字過大時，需要開辟較大陣列，不滿足實際要求，
雖然可以通過映射排名離散化和離線處理的手段，但不符合資料流實時讀入和查詢的在線要求，當然，如果只是為了得到資料流的結果而不強調實時性，所有查詢都可以在最后輸出，這種離線處理依然可行，
References:
[1] 資料結構與演算法分析：Java語言描述-Mark Allen Weiss
[2] 程式員面試金典-Gayle Laakmann McDowell
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/278380.html
標籤：其他
上一篇：leetcode 28 實作strStr() [KMP]
下一篇：不用加號的加法