算法分析与设计►未分类

Split Array

  • 问题来源
  • 问题简介

    给你一个有序数组（允许重复数字出现），要求把他分成若干个连续的无重复数字的数组，且每个数组长度需大于3。

解题思路


从左到右遍历，则对于每次遍历的数字

若是连续的

将该数字添加到可添加的长度最小的数组中

若是重复的或者不连续的

新开一个数组储存

若该数字与某个新开数组的最大值不为连续且该新开数组长度小于3

由于所遍历的数组是有序的，则之后遍历的数字都将无法被添加到该新开数组中，则表示分解操作失败


时间复杂度 空间复杂度
O(未知) O(未知)

Code

class Solution {
public:
    bool isPossible(vector<int>& nums) {
        int s = 0, e = nums.size();
        vector<stack<int>> severals;
        int minIndex = severals.size(), minSize = e;
        vector<int> canAdd;

        for (;s != e;s++) {
            canAdd.clear();

            minIndex = severals.size();
            minSize = e;

            for (int i = 0; i < severals.size(); i++) {
                int top = severals[i].top(), s_s = severals[i].size();
                if (top != nums[s]) {
                    if (nums[s] - top <= 1) {
                        canAdd.push_back(i);
                        if (s_s < minSize) {
                            minIndex = i;
                            minSize = s_s;
                        }
                    } else if (s_s < 3) {
                        return false;
                    }
                }
            }
            if (!canAdd.size()) {
                severals.push_back(stack<int>());
                minSize = 0;
            }
            severals[minIndex].push(nums[s]);
        }

        bool valid = true;
        for (int i = 0; i < severals.size(); i++) {
            if (severals[i].size() < 3) {
                valid = false;
                break;
            }
        }
        return valid;
    }
};

运行结果

Split Array