剑指offer45扑克牌顺子

剑指offer45



1、排序+遍历
满足以下2条规则即可：（1）判断是否有除0以外的重复 （2）最大最小之间相差是否大于4
无需计较0的数量，满足以上，少的0都会补上
因为排序原因，时间复杂度O(nlogn) 空间复杂度O(1)
个人代码

//只要保证11、范围长度在5个数以内，2、除0外不能重复,就可以保证连续，
//无论0几个缺啥补啥,只要没重复，就不可能不够补
//时间复杂度O(n+nlogn) 即O(nlogn)  空间复杂度O(1)
    bool IsContinuous( vector<int> numbers ) {
        sort(numbers.begin(),numbers.end()); //排序
        int max=numbers[4]; //最大值
        int index=0; //0数量
        while(numbers[index]==0)
        {
            ++index; 
        }
        int min=numbers[index]; //除0外最小值
        if((max-min)>4) return false; //最大最小之间顶多差4个数
        for(int i=index;i<4;i++) //除0外的数不能有重复
        {
            if(numbers[i]==numbers[i+1])
                return false;
        }
        return true;
    }

2、优化,萝卜插坑排序
上述时间复杂度高时因为排序原因，而我们实际想做的是计算最大最小值，以及判断是否除0以外的重复
观察发现，在知道大小之后，我们的数组类似于0-n-1分别不同的数字排序，萝卜插坑排序可以优化时间复杂度到O(n)，对于坑被占的情况排序中止，直接返回不连续。
第一次遍历，0调整到最前面，顺便找min max 并初步判断
第二次，0之后的位置间插坑排序，判断是否有重复值
时间复杂度：O（n） 空间复杂度：O(1)
个人代码

  bool IsContinuous( vector<int> numbers ) {
        int index=0; //0的待入位置
        int min=-1;
        int max=-1;
        //第一次遍历，0移动到最前面，找出min max
        for(int i=0;i<numbers.size();i++)
        {
            if(numbers[i]==0) //发现0,0与非0数字交换位置，
            {
                int temp=numbers[index];
                numbers[index++]=numbers[i];
                numbers[i]=temp;
            }
            else //找0以外ia最大最小值
            {
                if(min==-1&&max==-1)  //min max初始化
                {
                    min=numbers[i];
                    max=numbers[i];
                }
                else
                {
                    if(numbers[i]<min)
                        min=numbers[i];
                    if(numbers[i]>max)
                        max=numbers[i];
                }
            }
        }
        if((max-min)>(numbers.size()-1)) //数字范围超了
            return false;
        //插坑排序，找重复值
        //第一次遍历后，index位置及以后都是非0数字，最小值min应放在0位置
        //任意数X应放在X-min位置，比如X=min+1,放在1位置
        for(int i=index;i<numbers.size();i++)
        {
            if(numbers[i]!=(i+min))
            {
                int pos=numbers[i]-min;//numbers[i]应该放入的位置
                if(numbers[pos]==numbers[i]) //若应该放入的位置已经有相同值，即也放正确的值，则重复
                    return false;
                //否则交换与numbers[i]交换
                if(numbers[pos]!=0)
                {
                    int temp=numbers[pos];
                    numbers[pos]=numbers[i];
                    numbers[i]=temp;
                    i--;//i位置显然需要重新判断
                }
                else //合适位置是0视作空，直接放入，原有位置视为空
                {
                    numbers[pos]=numbers[i];
                    numbers[i]=0; //
                }
            }
        }
        return true;
    }