Javaデータ構造シリーズ(1)——自己平衡ツリー

TreeSet set=TreeSet<>();

set.ceiling(x)    //  set     x    ，      
set.floor(x)      //  set     x    ，      
set.size()        //       
set.remove()      //       
set.add()         //        

 
  
 
  
4、運用——LeetCode 220題
テーマの説明:1つの整数の配列を与えて、配列の中で2つの異なるインデックスiとjがあるかどうかを判断して、 nums[i]と nums [j] の差の絶対値は最大tであり、iとjの差の絶対値は最大kである.
  : nums = [1,2,3,1], k = 3, t = 0
  : true
  
分析:この問題に対して、私たちが最も主要なのはスライドウィンドウを運用して、それからウィンドウ内の値が要求を満たすかどうかを探すことです.検索問題では、自己平衡ツリーを使用して、対数レベルで実装できます.
アルゴリズム:ウィンドウ内の値をセルフバランスツリーで保存します.
ツリー内でxに等しい最小値sより大きい、s<=x+tの場合、true 
が戻る.
ツリーにおいてxに等しい最大値g未満、x<=g+tの場合、true 
が戻る.
はxをツリーに格納し、ツリー内の要素がウィンドウサイズkより大きい場合、最小ツリーに入る要素を削除し、終了するまでループする.
  
  ：  （LeetCode）
  ：https://leetcode-cn.com/problems/contains-duplicate-iii
          。           ，          。
  
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
　　TreeSet set=new  TreeSet<>();
　　for(int i=0;ii){
　　　　Integer s=set.ceiling(nums[i]);
　　　　if(s!=null && s<=nums[i]+t) return true;
　　　　Integer g=set.floor(nums[i]);
　　　　if(s!=null && nums[i]<=g+t) return true;
　　　　set.add(nums[i]);
　　　　if(set.size()>k){
　　　　　　set.remove(nums[i-k]);
　　　　}
　　}
　　return false;
}
  
続きはまだ...