博客

给定一个整数数组nums和一个正整数k，请判断，正整数k是否能将数组nums再划分成若干个长度为k的连续数字的数组？

例：

输入：nums = [1,2,3,3,4,4,5,6], k = 4
输出：true
解释：数组可以分成 [1,2,3,4] 和 [3,4,5,6]。

题解：

这里我使用了优先队列PriorityQueue，优先队列PriorityQueue.poll()能保证取出的元素永远是权值最小的。

代码如下：

class Solution {
    public boolean isPossibleDivide(int[] nums, int k) {
        int len = nums.length;
        // 数组长度一定要是k的倍数才可以划分
        if(len % k != 0){
            return false;
        }

        // 优先队列的作用是能保证每次取出的元素都是队列中权值最小的
        PriorityQueue<Integer> heap = new PriorityQueue<>(len);
        for(int num : nums){
            heap.offer(num);
        }

        while(!heap.isEmpty()){
            // top：队列中权值最小的元素
            int top = heap.poll();

            // 除了top，再取k-1个元素
            for(int i =1; i < k ; i++){
                // i是相对于top的偏移量
                if(!heap.remove(top + i)){
                    return false;
                }
            }
        }
        return true;
    }
}