劍指offer-撲克牌順子

題目描述

LL今天心情特别好,因為他去買了一副撲克牌,發現裡面居然有2個大王,2個小王(一副牌原本是54張_)…他随機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子…LL不高興了,他想了想,決定大\小 王可以看成任何數字,并且A看作1,J為11,Q為12,K為13。上面的5張牌就可以變成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL決定去買體育彩票啦。 現在,要求你使用這幅牌模拟上面的過程,然後告訴我們LL的運氣如何， 如果牌能組成順子就輸出true，否則就輸出false。為了友善起見,你可以認為大小王是0。

思路（劍指offer書籍）

把數組排序，如果排序後的數組不是連續的（相鄰的兩個數字隔若幹個數字），但是有足夠的0可以補滿這兩個數字的空缺，這個數組實際上還是連續的。比如，數組排序之後為{0，1,3，4，5}，在1和3中間空缺一個2，剛好有一個0，可以當成2去填補這個空缺。

是以需要：

1. 把數組排序
2. 統計數組中0的個數

3. 統計排序之後數組中相鄰數字之間的空缺總數

   如果空缺的總數小于或者等于0的個數，那麼這個數組就是連續的；反之則不連續。

   （為什麼是小于等于，而不是等于 比如數組[3,0,0,0,0]，空缺數為3但是0個數為4）

   還需注意的是，數組中非0數字重複出現，則該數組不是連續的。

java實作

import java.util.Arrays;
public class Solution {
    public boolean isContinuous(int[] numbers) {
        int len = numbers.length;
        if (numbers == null || len ==0)
            return false;
        Arrays.sort(numbers);//數組排序
        int numOfZero = 0;//記錄數組中0的個數
        int numOfGap = 0;//記錄排序後數組中相鄰數字之間的空缺總數
        //記錄數組中0的個數
        for (int i = 0; i < len; i++) {
            if (numbers[i] == 0)
                ++numOfZero;
        }
        int small = numOfZero;//從第一個不是0的數字開始比較 前一個數字
        int big = small + 1;//後一個數字
        while (big < len) {//範圍  索引在len之内
            if (numbers[small] == numbers[big])//排序好的數字中有連續數字，說明有對子，不是順
                return false;
            numOfGap += numbers[big] - numbers[small] - 1;//統計排序後數組中相鄰數字之間的空缺總數
            small = big;
            big++;
        }
        if (numOfGap <= numOfZero)//空缺總數<0的總數  可以用0替代 可以成順
            return true;
        return false;
    }
}