# Leetcode - Divide Array in Sets of K Consecutive Numbers

violet posted @ Apr 02, 2020 09:10:49 AM in 算法 with tags hash Algorithm array Golang , 245 阅读

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
}```

(输入验证码)
or Ctrl+Enter