分割数组为连续子序列-白红宇

分割数组为连续子序列

阅读量：572 次

发布时间：2019-03-10

本文共 5860 字，大约阅读时间需要 19 分钟。

给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。如果可以完成上述分割，则返回 true ；否则，返回 false 。 示例 1：输入: [1,2,3,3,4,5]输出: True解释:你可以分割出这样两个连续子序列 : 1, 2, 33, 4, 5来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

文章目录

1. 解题思路

因为有最小长度限制所以尽量减少队列的数目让队列变得更长

每新计算一个数从已有的队列中最短的开始判断是否满足条件(队列最后一个元素+1等于当前值) 如果满足填入若不满足新建一个队列

最终判断是否每个队列的数组都大于等于3

2. 初始版本代码(超时)

public class LianshuZixulie {          public boolean isPossible(int[] nums) {           if (nums.length < 3) {               return false;        }        List
   
    
     > result = new ArrayList<>();        result.add(new ArrayList<>());        result.get(0).add(nums[0]);        for (int i = 1; i < nums.length; i++) {               int j = 0;            for (; j < result.size(); j++) {                   int last = result.get(j).get(result.get(j).size() - 1);                if (nums[i] == last + 1) {                       result.get(j).add(nums[i]);                    break;                }            }            if (j >= result.size()) {                   List
     
       temp = new ArrayList<>();                temp.add(nums[i]);                result.add(temp);            }            Collections.sort(result, Comparator.comparingInt(List::size));        }        for (List
      
        tmp: result) {               if (tmp.size() < 3) {                   return false;            }        }        return true;    }    public static void main(String[] args) {           int [] input = new int[] {   1,2,3,3,4,4,5,5};        System.out.println(new LianshuZixulie().isPossible(input));    }}

3. 优化排序(超时)

超出时间限制对排序部分优化一下去除不必要的操作

public class LianshuZixulie {       /**     * 从已存在的队列中找一个最短的可填的进去     * 找不到则新建一个队列     */    public boolean isPossible(int[] nums) {           if (nums.length < 3) {               return false;        }        List
   
    
     > result = new ArrayList<>();        result.add(new ArrayList<>());        result.get(0).add(nums[0]);        for (int i = 1; i < nums.length; i++) {               int j = 0;            for (; j < result.size(); j++) {                   int last = result.get(j).get(result.get(j).size() - 1);                if (nums[i] == last + 1) {                       result.get(j).add(nums[i]);                    // 从当前位置向后调整                    adjustNext(result, j);                    break;                }            }            if (j >= result.size()) {                   List
     
       temp = new ArrayList<>();                temp.add(nums[i]);                // 直接插入头部                result.add(0, temp);            }            //Collections.sort(result, Comparator.comparingInt(List::size));        }        return result.get(0).size() >= 3;    }    private void adjustNext(List
      
       
        > result, int i) {           for (int j = i + 1; j < result.size(); j++) {               if (result.get(j - 1).size() > result.get(j).size()) {                   Collections.swap(result, j-1, j);            }        }    }    public static void main(String[] args) {           int [] input = new int[] {   1,2,3,3,4,4,5,5};        System.out.println(new LianshuZixulie().isPossible(input));    }}

4. 最终版本

仍然超时，需要减少一下swap的次数（数组实现的列表 swap耗时较大）

改造一下adjustNext 函数

private void adjustNext(List
   
    
     > result, int i) {           int j;        // 减少操作交换的次数 以及每次swap的范围        for (j = i + 1; j < result.size(); j++) {               if (result.get(j).size() >= result.get(i).size()) {                   Collections.swap(result, i, j-1);                break;            }        }        // 如果没有发生交换        if (j >= result.size()) {               List
     
       temp = result.get(i);            for (int k = i; k < result.size() -1; k++) {                   result.set(k, result.get(k + 1));            }            result.set(result.size() -1, temp);        }    }

通过, 最终代码

import java.util.ArrayList;import java.util.Collections;import java.util.LinkedList;import java.util.List;/** * https://leetcode-cn.com/problems/split-array-into-consecutive-subsequences/ */public class LianshuZixulie {       /**     * 从已存在的队列中找一个最短的可填的进去     * 找不到则新建一个队列     */    public boolean isPossible(int[] nums) {           if (nums.length < 3) {               return false;        }        List
   
    
     > result = new ArrayList<>();        result.add(new ArrayList<>());        result.get(0).add(nums[0]);        for (int i = 1; i < nums.length; i++) {               int j = 0;            for (; j < result.size(); j++) {                   List
     
       curr = result.get(j);                int last = curr.get(curr.size() - 1);                if (nums[i] == last + 1) {                       result.get(j).add(nums[i]);                    // 从当前位置向后调整                    adjustNext(result, j);                    break;                }            }            if (j >= result.size()) {                   List
      
        temp = new ArrayList<>();                temp.add(nums[i]);                // 直接插入头部                result.add(0, temp);            }            //Collections.sort(result, Comparator.comparingInt(List::size));        }        return result.get(0).size() >= 3;    }    private void adjustNext(List
       
        
         > result, int i) { int j; // 减少操作交换的次数 for (j = i + 1; j < result.size(); j++) { if ((result.get(j).size() >= result.get(i).size()) && j-1 != i) { Collections.swap(result, i, j-1); break; } } if (result.get(i).size() > result.get(result.size() -1).size()) { List
         
           temp = result.get(i); for (int k = i; k < result.size() -1; k++) { result.set(k, result.get(k + 1)); } result.set(result.size() -1, temp); } } public static void main(String[] args) { int [] input = new int[] { 1,2,3,3,4,4,5,5}; System.out.println(new LianshuZixulie().isPossible(input)); }}