1296. 划分数组为连续数字的集合

╰半橙微兮° 2023-10-04 10:27 21阅读 0赞

给你一个整数数组 `nums` 和一个正整数 `k`，请你判断是否可以把这个数组划分成一些由 `k` 个连续数字组成的集合。  
如果可以，请返回 `True`；否则，返回 `False`。

**注意：**此题目与 846 重复：[https://leetcode-cn.com/problems/hand-of-straights/][https_leetcode-cn.com_problems_hand-of-straights]

**示例 1：**

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

**示例 2：**

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

**示例 3：**

输入：nums = [3,3,2,2,1,1], k = 3
    输出：true

**示例 4：**

输入：nums = [1,2,3,4], k = 3
    输出：false
    解释：数组不能分成几个大小为 3 的子数组。

**提示：**

*  `1 <= nums.length <= 10^5`
 *  `1 <= nums[i] <= 10^9`
 *  `1 <= k <= nums.length`

package Solution1296;
    
    import java.util.ArrayList;
    import java.util.Arrays;
    import java.util.List;
    
    class Solution {
    	public boolean isPossibleDivide(int[] nums, int k) {
    		Arrays.sort(nums);
    		ArrayList<List<Integer>> alal = new ArrayList<List<Integer>>();
    
    		ArrayList<Integer> al = new ArrayList<Integer>();
    		if (nums.length > 0) {
    			al.add(nums[0]);
    
    		}
    		alal.add(al);
    		for (int i = 1; i < nums.length; i++) {
    			boolean find = false;
    			for (int j = alal.size() - 1; j > -1; j--) {
    				if (nums[i] == alal.get(j).get(alal.get(j).size() - 1) + 1 && alal.get(j).size() < k) {
    					alal.get(j).add(nums[i]);
    					find = true;
    					break;
    				}
    			}
    			if (find == false) {
    				ArrayList<Integer> temp = new ArrayList<Integer>();
    				temp.add(nums[i]);
    				alal.add(temp);
    			}
    
    		}
    		System.out.println(alal);
    		for (int i = 0; i < alal.size(); i++) {
    			if (alal.get(i).size() != k) {
    				return false;
    			}
    		}
    		return true;
    
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    		int[] nums = { 10, 9, 8, 1, 2, 3, 2, 3, 4, 4, 5, 6, 10, 11, 12 };
    		int k = 3;
    		System.out.println(sol.isPossibleDivide(nums, k));
    
    	}
    }

超时

他人通过的答案

package Solution1296;
    
    import java.util.Arrays;
    import java.util.HashMap;
    import java.util.Map;
    
    class Solution {
    
    	public boolean isPossibleDivide(int[] nums, int k) {
    		if (nums.length % k != 0)
    			return false;
    		if (k == 1)
    			return true;
    		Arrays.sort(nums);
    		Map<Integer, Integer> map = new HashMap<>();
    		for (int num : nums)
    			map.put(num, map.getOrDefault(num, 0) + 1);
    		for (int num : nums) {
    			if (map.get(num) != 0) {
    				int start = num;
    				int end = num + k - 1;
    				while (start <= end) {
    					Integer v = map.get(start);
    					if (v != null && v > 0)
    						map.put(start++, v - 1);
    					else
    						return false;
    				}
    			}
    		}
    		return true;
    	}
    
    	public static void main(String[] args) {
    
    		Solution sol = new Solution();
    		int[] nums = { 10, 9, 8, 1, 2, 3, 2, 3, 4, 4, 5, 6, 10, 11, 12 };
    		int k = 3;
    		System.out.println(sol.isPossibleDivide(nums, k));
    
    	}
    }

[https_leetcode-cn.com_problems_hand-of-straights]: https://leetcode-cn.com/problems/hand-of-straights/