LeetCode日本語修行4日目- [220- Contains Duplicate III]

Contains Duplicate III

参考https://leetcode.com/problems/contains-duplicate-iii/

問題の内容

整数配列numsと2つの整数kとt、
配列中に
abs(nums[i] - nums[j]) <= t
abs(i - j) <= k
条件を満たすとなるiとjがあればtrueを返す。

例

例1:
Input: nums = [1,2,3,1], k = 3, t = 0
Output: true

例2:
Input: nums = [1,0,1,1], k = 1, t = 2
Output: true

例3:
Input: nums = [1,5,9,1,5,9], k = 2, t = 3
Output: false

ヒント:

0 <= nums.length <= 2 * 104
-231 <= nums[i] <= 231 - 1
0 <= k <= 104
0 <= t <= 231 - 1

---

一番分かりやすいのは、ループ処理ですね,注意するべきのは、Longです
今回のテストcaseの中に

[2147483647,-1,2147483647]
1
2147483647

他の似ているcaseもうあります、
Intの範囲は 有効な値は -2147483648から2147483647ので。処理する必要。
　

class Solution {
    fun containsNearbyAlmostDuplicate(nums: IntArray, k: Int, t: Int): Boolean {
        if(k<0 || t < 0){
            return false
        }

        for(i in 0 until nums.size){
           for(j in Math.max(i-k,0) until Math.min(nums.size,i+k) ){
               if(Math.abs(nums[i].toLong() - nums[j].toLong()) <= t.toLong() ){
                   if(j == i){
                       continue
                   }
                   return true
               }
           } 
        }
        return false
    }
}

ですが.....この結果

2972 ms  	40 MB

長過ぎ....
それを改善する為、バケットソートを使います。

バケットソート（英: bucket sort）は、ソートのアルゴリズムの一つ。バケツソート、ビンソート（英: bin sort）などともいう。バケツ数 k 個使った場合、オーダーはO(n + k)となり、ソートする要素数nとk を無関係にできる場合線形時間ソートとなるが、要素間の全順序関係を用いるソートとは異なり、キーの取りうる値がk種類である、という入力により強い制限を要求するソートである。

参考：https://ja.wikipedia.org/wiki/%E3%83%90%E3%82%B1%E3%83%83%E3%83%88%E3%82%BD%E3%83%BC%E3%83%88

今回は、バケツの長さはt＋１、nums[i]とnums[j]は一つのバケツに格納されていますなら、trueを返す
隣のバケツの場合、二つの差は　<= t　なら、同じtrueを返す
var bucketLength = t+1
t+1の原因は
もしt=3即ちMax-Min=3この時、バケツ中は1,2,3,4バケツの長さは４です
nums[i]<0の場合0が含めないので、０からじゃない、１から、調整が必要です

class Solution {
    fun containsNearbyAlmostDuplicate(nums: IntArray, k: Int, t: Int): Boolean {

        if(k < 0 || t < 0){
            return false
        }
        
        var map = HashMap<Long,Long>()
        var bucketLength = t+1

        for(i in 0 until nums.size){
            var id: Long = getBucketID(nums[i].toLong(),bucketLength.toLong())

            if(map.containsKey(id)){
                return true
            }
            if(map.containsKey(id-1) && Math.abs(nums[i] - map.get(id-1)!!) < bucketLength){
                return true
            }

            if(map.containsKey(id+1) && Math.abs(nums[i] - map.get(id+1)!!) < bucketLength){
                return true
            }

            map.put(id,nums[i].toLong())
            if(i >= k){
                map.remove(getBucketID(nums[i-k].toLong(),bucketLength.toLong()))
            }    
        }
        return false
    }

    fun getBucketID(value: Long,length: Long): Long{
        if(value >= 0){
            return value/length
        }else{
            return (value+1)/length - 1
        }
    }
}