左边升序右边降序的数组o1时间内计算不重复元素个数

问题

左边升序右边降序的数组o1时间内计算不重复元素个数

比如：[1,2,3,4,4,5,10,9,5,3,1,0]， 返回8

要求：空间复杂度o(1), 时间复杂度o(n)

分析

讲真，从来没思考过o1空间复杂度下，要怎么破解这个问题。今天恰好遇到了，就思考下。太菜了，想了好久

下面讲讲思路吧

1. 既然是有规律的升序降序数组,重复的元素都是连在一起的。那么我们顺序筛一遍就可以知道左半部分有多少重复，右半部分有多少重复。时间复杂度O(n)，空间复杂度O(1)
2. 左右两头比对，相等就计数器-1。不相等就看大小，右边大则右边下标-1，否则左边下标-1，继续比对。时间复杂度O(n)，空间复杂度O(1)

实现代码

。。。。等我去测试下。。。

蛮高兴，自己测试了下，没啥问题

function process($array){
    $len = count($array);
    $total = $len;
    $left = 0;
    $right = count($array)-1;

    // 空数组返回0
    if($len < 2){
        return $len;
    }

    // 去掉升序部分的重复，去掉降序部分的重复,O(n)
    // 两头开始检查，如果右边当前元素出现在左边，total-1
    $pos = 0;
    while($pos + 1 < $len){
        if($array[$pos] == $array[$pos+1]){    // 出现重复元素，-1
            $total -= 1;                        
        }
        $pos ++;
    }

        // 两头去找
    while($left < $right){
        if($array[$left] == $array[$right]){
            $total -= 1;
            $left += 1;
            $right -= 1;
        }else if($array[$left] > $array[$right]){
            $right -= 1;
        }else{
            $left += 1;
        }
    }

    return $total;
}

echo process([1, 9, 10, 11, 30, 11]) . "\n";
echo process([1,2,3,4,4,5,10,9,5,3,1,0]) . "\n";

优化

容我想想