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

楚天乐 148 0 条

问题

左边升序右边降序的数组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";

优化

容我想想



发表我的评论
昵称 (必填)
邮箱 (必填)
网址
执行时间: 52.083015441895 毫秒