重庆住房城乡建设厅官方网站,手机app软件开发机构,江苏网站建设推广,高端品牌网站制作给一个已经排好序的升序数组#xff0c;其中每个元素都会重复2次#xff0c;只有一个元素只有一个#xff0c; 找出这个只有一个的元素。 要求时间复杂度在O(logn), 空间复杂度在O(1).
思路#xff1a;
时间复杂度为O(logn), 让人想到了binary search.
因为时间复杂度为…
给一个已经排好序的升序数组其中每个元素都会重复2次只有一个元素只有一个 找出这个只有一个的元素。 要求时间复杂度在O(logn), 空间复杂度在O(1).
思路
时间复杂度为O(logn), 让人想到了binary search.
因为时间复杂度为O(1), 所以不能用一个数组来保存每个元素出现的次数。
不过每个元素也就出现2次而且是排好序的也就是说相同的元素都是在一起的。 可以用一个cnt, 元素第一次出现时cnt 1, 第2次出现时cnt 0, 那么只出现一次的元素cnt就无法清0于是就被找出来了。 但是这种方法需要遍历数组时间复杂度为O(n), 也能通过测试。 public int singleNonDuplicate(int[] nums) {int cnt 1;int n nums.length;if(n 1) return nums[0];for(int i 1; i n; i) {if(nums[i] ! nums[i-1]) {if(cnt 1) return nums[i-1];else cnt 1;} else {cnt 0;}}return nums[n-1];}下面看一下binary search.
为什么能用binary search呢 因为每个元素出现2次长度为偶数只有一个元素出现了1次 包含出现了1次的元素的部分长度一定是奇数。
我们可以判断奇数的长度出现在左边还是右边把left, right指针卡在奇数长度的部分。
举个例子 22334 [0] [1] [2] [3] [4] left 0, right 4, mid 2 右半边的长度不含mid本身为right - mid 2, 长度为偶数
但是发现没有nums[mid]和nums[mid1]两个数是一样的 现在的长度right-mid 把两个相同的元素拆开了违背了刚才判断的标准 2个相同的元素都在一起才符合长度为偶数的标准拆开了就不能按照长度为奇偶来判断了。
所以要比较nums[mid]和nums[mid1]两个元素如果相同把nums[mid]也算进右边 所以现在右边长度为奇数可以判断单个的元素在右边移动left mid 2跳过重复元素。 那如果是下面的例子 12233, 可以看到右边长度为偶数这时要移动right mid - 2跳过重复元素
直到nums[mid] 和 nums[mid 1], nums[mid-1]都不相等, 返回nums[mid]. public int singleNonDuplicate(int[] nums) {int n nums.length;if(n 1) return nums[0];int left 0;int right n - 1;while(left right) {int mid left (right - left)/2;boolean isEvenLen ((right - mid) % 2 0);if(mid 1 nums[mid] nums[mid-1]) {if(isEvenLen) right mid-2;else left mid 1;//重复元素算进右边长度} else if(mid n - 1 nums[mid] nums[mid1]) {if(isEvenLen) left mid 2; //算进重复元素后右边长度为奇数单个元素在右边else right mid - 1;} else {return nums[mid];}}return -1;}
