快捷搜索:

1296 划分数组为连续数字的集合(treemap)

1. 问题描述:

2. 思路分析:

① 因为给出的数组可能是无序的,所以我们需要使用map来进行计数,因为求解的是连续的一组数字,所以需要按照从小到大的顺序进行排列,所以我们首先可以对数组遍历的时候使用treemap对数组中出现的数字进行计数,并且使用treemap得到的键是按照从小到大的顺序进行排列的,这样方便我们进行分组

② map中放置的键值对不容易操作,使用treemap进行计数之后那么我们需要将对应的数字映射到数组中,这样可以使用下标对分组的数字进行操作,对当前的的k个数字进行判断,看一下这一组的k个数字是否连续,也就是相邻两个数字的差值是否是1,加入不是1那么说明存在不是一组的数字,直接返回false

③ 对于一组的k个数字我们相应地移除掉当前分组的首个元素的值,最后检查数组元素的值是否是0,假如全部是0那么满足条件

3. 代码如下:

class Solution {
 /*可以使用map来进行计数, 先将结果放入数组中然后先检查这k个元素是否连续, 不连续直接返回false, 连续则依次取出k个元素*/
   public boolean isPossibleDivide(int[] nums, int k) {
        /*使用TreeMap进行键的自定义排序*/
        Map<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < nums.length; ++i){
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        int [][]rec = new int[map.size()][2];
        int n = 0;
        for (Map.Entry<Integer, Integer> entry : map.entrySet()){
            rec[n][0] = entry.getKey();
            rec[n][1] = entry.getValue();
            ++n;
        }
        int len = map.size();
        int count = 0;
        for (int i = 0; i <= len - k; ++i){
            if (rec[i][1] == 0)continue;
            /*检查k个元素是否连续*/
            for (int j = i + 1; j < i + k && j < map.size(); ++j){
                if (rec[j - 1][0] + 1 != rec[j][0]) return false;
            }
            /*将取出的k个元素减掉*/
            int t = rec[i][1];
            for (int j = i; j < i + k; ++j) {
                rec[j][1] -= t;
            }
        }
        for (int i = 0; i < len; ++i) if (rec[i][1] != 0) return false;
        return true;
    }
}
经验分享 程序员 微信小程序 职场和发展