数组去重

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

问题 左边升序右边降序的数组o1时间内计算不重复元素个数 比如:[1,2,3,4,4,5,10,9,5,3,1,0], 返回8 要求:空间复杂度o(1), 时间复杂度o(n) 分析 讲真,从来没思考过o1空间复杂度下,要怎么破解这个问题。今天恰好遇到了,就思考下。太菜了,想了好久 下面讲讲思路吧 既然是有规律的升序降序数组,重复的元素都是连在一起的。那么我们顺序筛一遍就可以知道左半部分有多少重复,右半部分有多少重复。时间复杂度O(n),空间复杂度O(1) 左右两头比对,相等就计数器-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;...
执行时间: 31.000137329102 毫秒