溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
小編給大家分享一下golang刷leetcode技巧之如何實現數字流的秩，相信大部分人都還不怎么了解，因此分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后大有收獲，下面讓我們一起去了解一下吧！
假設你正在讀取一串整數。每隔一段時間，你希望能找出數字 x 的秩(小于或等于 x 的值的個數)。請實現數據結構和算法來支持這些操作，也就是說：
實現 track(int x) 方法，每讀入一個數字都會調用該方法；
實現 getRankOfNumber(int x) 方法，返回小于或等于 x 的值的個數。
注意：本題相對原題稍作改動
示例:
輸入:
["StreamRank", "getRankOfNumber", "track", "getRankOfNumber"]
[[], [1], [0], [0]]
輸出:
[null,0,null,1]
提示：
x <= 50000
track 和 getRankOfNumber 方法的調用次數均不超過 2000 次
解題思路
1，這是二分查找的拓展
2，包含二分查找和二分插入
3，與二分查找的區別是，找到mid位置后，如果mid位置的值<=target ,需要后移mid
代碼實現
type StreamRank struct {data []int}func Constructor() StreamRank {return StreamRank{}}func (this *StreamRank) getMid(x int)int{i:=0j:=len(this.data)-1mid:=(i+j)/2for i+1<j{if this.data[mid]==x{break}if this.data[mid]<x{i=mid+1}else{j=mid-1}mid=(i+j)/2}for mid <len(this.data) &&this.data[mid]<=x && mid<len(this.data){mid++}return mid}func (this *StreamRank) Track(x int) {if len(this.data)==0{this.data=append(this.data,x)return}mid:=this.getMid(x)d:=this.data[mid:]this.data=append(this.data[:mid:mid],x)this.data=append(this.data,d...)return}func (this *StreamRank) GetRankOfNumber(x int) int {if len(this.data)==0{return 0}mid:=this.getMid(x)return mid}/*** Your StreamRank object will be instantiated and called as such:* obj := Constructor();* obj.Track(x);* param_2 := obj.GetRankOfNumber(x);*
以上是“golang刷leetcode技巧之如何實現數字流的秩”這篇文章的所有內容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內容對大家有所幫助，如果還想學習更多知識，歡迎關注億速云行業資訊頻道！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
