難度：中等

題目：

????給你一個按升序排序的整數(shù)數(shù)組?num(可能包含重復(fù)數(shù)字)，請你將它們分割成一個或多個長度為 3 的子序列，其中每個子序列都由連續(xù)整數(shù)組成。

????如果可以完成上述分割，則返回?true?；否則，返回?false?。

------------------------------------------------------

思考：

????題目要求，把數(shù)組分割成一或多個連續(xù)的子串，那就是要把盡可能多的數(shù)字弄成子串，看著有點(diǎn)像可以貪心。

????如果用貪心的話，例如實(shí)例2，先盡可能多的從1開始把12345排成一個子序列，然后剩下345排成另一個子序列。

????誒好像可以。

????但是到了示例1這種就8行了。先拿出12345，然后就會只剩下3，不成立，但其實(shí)他卻是成立的。

????其實(shí)，上面解釋這種只是普通的一般的貪心，我們可以改變一下，升級一下，非一般的貪心。

????一個一個地貪心。? ?

思路：

• 先用兩個hashMap，一個countNum用來記錄數(shù)字出現(xiàn)次數(shù)，一個tail記錄以每個數(shù)字num結(jié)尾的子序列數(shù)。

• 然后遍歷數(shù)組，從頭開始，

• 先判斷countNum的對應(yīng)數(shù)字(例如X)數(shù)量是否＞0，如果是則再去查找有沒有以數(shù)字X-1為結(jié)尾的子X序列，有則把數(shù)字X續(xù)上，tail的X-1結(jié)尾的序列數(shù)量-1，X結(jié)尾的+1，countNum中的X數(shù)量-1。

• 繼續(xù)判斷下一位。

• 如果全部都能連上就是成功。否則有一個不能連上就是失敗。

以示例1來說，

????首先看1，先去countNum查找1的數(shù)量，如果>0個，則再去查找tail。如果有以1前一位(也就是0)結(jié)尾的，就在后面再續(xù)上，然后countNum的num的對應(yīng)數(shù)量-1，tail的前一位的數(shù)量-1，1結(jié)尾的+1；如果tail沒有以前一位結(jié)尾話，就去看后兩位，2和3的countNum是不是同時>0，如果是則連成子串，對應(yīng)的123的countNum-1，tail對應(yīng)的3數(shù)量+1。

? ??然后看2，因?yàn)樯厦?23連成了，123都-1，countNum的2數(shù)量=0.

? ? 再看3，上面減了1，countNum的3數(shù)量為1，同樣查找tail，沒有以前一位(2)結(jié)尾的，直接查看后兩位，有，連成子序列345，countNum各個數(shù)-1，tail為5的+1。

? ? 最后都可以連上，成功。

代碼：

public boolean isPossible(int[] nums) { // 用一個哈希表統(tǒng)計每個數(shù)字出現(xiàn)的次數(shù) Map countNum = new HashMap<>(); for (int num : nums) countNum.put(num, countNum.getOrDefault(num, 0) + 1); // 定義一個哈希表記錄最長的子序列 Map tail = new HashMap<>(); for (int num : nums) { int count = countNum.getOrDefault(num, 0); if (count <= 0) {//當(dāng)前元素已經(jīng)用完，直接跳過 continue; } else if (tail.getOrDefault(num - 1, 0) > 0) {//前面還有數(shù)字，可以構(gòu)成以num結(jié)尾的子序列 countNum.put(num, count - 1); tail.put(num - 1, tail.get(num - 1) - 1);//覆蓋當(dāng)前最長的子序列 tail.put(num, tail.getOrDefault(num, 0) + 1);//當(dāng)前以num結(jié)尾的子序列+1 } else if (countNum.getOrDefault(num + 1, 0) > 0 && countNum.getOrDefault(num + 2, 0) > 0) {//前面無數(shù)字構(gòu)成子序列后，判斷能不能跟后面的構(gòu)成子序列 countNum.put(num, count - 1); countNum.put(num + 1, countNum.get(num + 1) - 1); countNum.put(num + 2, countNum.get(num + 2) - 1); tail.put(num + 2, tail.getOrDefault(num + 2, 0) + 1);//當(dāng)前以num+2結(jié)尾的子序列+1 } else return false;//前后不能構(gòu)成子序列則不成立 } return true;}

時間復(fù)雜度：兩個獨(dú)立的循環(huán)，一個記錄各個數(shù)字個數(shù)，一個遍歷數(shù)字情況。所以是O(n)

空間復(fù)雜度：兩個獨(dú)立的哈希表存儲數(shù)字個數(shù)和子序列數(shù)，所以是O(n)

----------------------------------完--------------------------------

淦里良?xì)G

總結(jié)

以上是生活随笔為你收集整理的序列每天从0开始_【算法打卡】分割数组为连续子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。