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; } }
上一篇:
IDEA上Java项目控制台中文乱码