Leetcode - Divide Array in Sets of K Consecutive Numbers

https://leetcode.com/problems/divide-array-in-sets-of-k-consecutive-numbers/

https://leetcode.com/problems/hand-of-straights

Given an array of integers nums and a positive integer k, find whether it's possible to divide this array into sets of k consecutive numbers
Return True if it's possible otherwise return False.

Example 1:

Input: nums = [1,2,3,3,4,4,5,6], k = 4
Output: true
Explanation: Array can be divided into [1,2,3,4] and [3,4,5,6].

1. Count frequency for every element(e.g. using hash)

2. Sort keys of hash

3. Start from smallest key n, run a loop from n to n + k. Minus count for every element with first frequency.

4. If there's any count smaller than 0, return false

element in the first line and frequency in the second line, k = 4

1 2 3 4 5

3 3 3 2 4

After first round of minus, the count for 4 is  -1. It can't form a consecutive array, so return false.

type Num struct {
    num int
    count int
}

func isPossibleDivide(nums []int, k int) bool {
    hash := map[int]*Num{}
    for _, n := range nums {
        _, ok := hash[n]
        if !ok {
            hash[n] = &Num{
                num: n,
                count: 1,
            }
        } else {
            hash[n].count++
        }
    }
    
    keys := []int{}
    for key, _ := range hash {
        keys = append(keys, key)
    }
    sort.Ints(keys)
    
    for i := 0; i < len(keys); i++ {
        n := keys[i]
        if hash[n].count > 0 {
            minus := hash[n].count
            for j := n; j < n + k; j++ {
                val, ok := hash[j]
                if !ok {
                    return false
                }
                if val.count < minus {
                    return false
                }
                hash[j].count -= minus
            }
        }
    }
    return true
}

• 相关文章
• 全局相关文章