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+1、nums[i]とnums[j]は一つのバケツに格納されていますなら、trueを返す
隣のバケツの場合、二つの差は <= t なら、同じtrueを返す
var bucketLength = t+1
t+1の原因は
もしt=3
即ちMax-Min=3
この時、バケツ中は1,2,3,4
バケツの長さは4
です
nums[i]<0
の場合0が含めないので、0からじゃない、1から、調整が必要です
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
}
}
}
Author And Source
この問題について(LeetCode日本語修行4日目- [220- Contains Duplicate III]), 我々は、より多くの情報をここで見つけました https://qiita.com/Aethey/items/9414d5994d50b54a9d5c著者帰属:元の著者の情報は、元のURLに含まれています。著作権は原作者に属する。
Content is automatically searched and collected through network algorithms . If there is a violation . Please contact us . We will adjust (correct author information ,or delete content ) as soon as possible .