leetcode: 128. Longest Consecutive Sequence

문제링크

풀이1

class Solution {
    private fun getParent(parents: Array<Int>, x: Int): Int {
        if (x == parents[x]) return x
        return getParent(parents, parents[x])
    }
    
    private fun union(parents: Array<Int>, lengths: Array<Int>, x: Int, y: Int) {
        val xParent = getParent(parents, x)
        val yParent = getParent(parents, y)
        if (xParent < yParent) {            
            parents[yParent] = xParent
            lengths[xParent] += lengths[yParent]
        } else {
            parents[xParent] = yParent
            lengths[yParent] += lengths[xParent]
        }
    }
    
    fun longestConsecutive(nums: IntArray): Int {
        val size = nums.size
        val parents = Array(size) { 0 }
        val lengths = Array(size) { 1 }
        val valToIndex = hashMapOf<Int, Int>()
        var answer = 0        
        repeat(size) { index -> parents[index] = index }
        nums.forEachIndexed { index, num -> 
            if (!valToIndex.containsKey(num)) {
                if (valToIndex.containsKey(num - 1)) union(parents, lengths, index, valToIndex[num - 1]!!)
                if (valToIndex.containsKey(num + 1)) union(parents, lengths, index, valToIndex[num + 1]!!)
                valToIndex[num] = index    
            }            
        }
        parents.forEachIndexed { index, parent -> 
            if (parent == index && answer < lengths[index]) {
                answer = lengths[index]
            }
        }
        return answer
    }
}

• Default
  

• union(parents, lengths, 1, 4)
  

• union(parents, lengths, 3, 5)
  

• union(parents, lengths, 4, 5)
  

풀이2

import kotlin.math.max

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val hashMap = hashMapOf<Int, Int>()
        var answer = 0
        nums.forEach { num ->
            if (!hashMap.containsKey(num)) {
                val left = hashMap[num - 1] ?: 0
                val right = hashMap[num + 1] ?: 0
                val length = left + right + 1
                hashMap[num] = length
                answer = max(answer, length)
                hashMap[num - left] = length
                hashMap[num + right] = length
            }
        }
        return answer
    }
}

• hashMap[100] = 0 + 0 + 1 = 1
• hashMap[4] = 0 + 0 + 1 = 1
• hashMap[200] = 0 + 0 + 1 = 1
• hashMap[1] = 0 + 0 + 1 = 1
• hashMap[3] = 1 + 0 + 1 = 2
• hashMap[2] = 1 + 2 + 1 = 4

풀이3

import kotlin.math.max

class Solution {
    fun longestConsecutive(nums: IntArray): Int {
        val numSet = hashSetOf<Int>()
        var answer = 0
        nums.forEach { num -> 
            numSet.add(num)
        }
        nums.forEach { num -> 
            if (numSet.remove(num)) {
                var point = num
                var length = 1
                while (numSet.remove(point - 1)) point--
                length += (num - point)
                
                point = num
                while (numSet.remove(point + 1)) point++
                length += (point - num)
                
                answer = max(length, answer)
            }
        }
        return answer
    }
}

• numSet.remove(100)
• numSet.remove(4) -> numSet.remove(3) -> numSet.remove(2) -> numSet.remove(1)