工信网备案网站,跨境电商平台介绍,做一名网络写手去那个网站好,长沙网站推广系统文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题#xff1a;有序数组中的单一元素
出处#xff1a;540. 有序数组中的单一元素
难度
4 级
题目描述
要求
给定一个仅由整数… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法一思路和算法代码复杂度分析 解法二思路和算法代码复杂度分析 题目
标题和出处
标题有序数组中的单一元素
出处540. 有序数组中的单一元素
难度
4 级
题目描述
要求
给定一个仅由整数组成的升序数组其中每个元素都出现两次除了一个元素只出现一次。
返回只出现一次的元素。
要求时间复杂度是 O(log n) \texttt{O(log n)} O(log n)空间复杂度是 O(1) \texttt{O(1)} O(1)。
示例
示例 1
输入 nums [1,1,2,3,3,4,4,8,8] \texttt{nums [1,1,2,3,3,4,4,8,8]} nums [1,1,2,3,3,4,4,8,8] 输出 2 \texttt{2} 2
示例 2
输入 nums [3,3,7,7,10,11,11] \texttt{nums [3,3,7,7,10,11,11]} nums [3,3,7,7,10,11,11] 输出 10 \texttt{10} 10
数据范围 1 ≤ nums.length ≤ 10 5 \texttt{1} \le \texttt{nums.length} \le \texttt{10}^\texttt{5} 1≤nums.length≤105 0 ≤ nums[i] ≤ 10 5 \texttt{0} \le \texttt{nums[i]} \le \texttt{10}^\texttt{5} 0≤nums[i]≤105
解法一
思路和算法
由于给定的数组已经排序因此相同元素在数组中一定位于相邻的位置。对于只出现一次的元素该元素的左边和右边各有偶数个元素。假设只出现一次的元素位于下标 index \textit{index} index考虑下标 x x x 处的元素 x ≠ index x \ne \textit{index} xindex。 当 x index x \textit{index} xindex 时只出现一次的元素在下标 x x x 的右边。如果 x x x 是偶数则 nums [ x ] nums [ x 1 ] \textit{nums}[x] \textit{nums}[x 1] nums[x]nums[x1]如果 x x x 是奇数则 nums [ x ] nums [ x − 1 ] \textit{nums}[x] \textit{nums}[x - 1] nums[x]nums[x−1]。 当 x index x \textit{index} xindex 时只出现一次的元素在下标 x x x 的左边。如果 x x x 是偶数则 nums [ x ] nums [ x − 1 ] \textit{nums}[x] \textit{nums}[x - 1] nums[x]nums[x−1]如果 x x x 是奇数则 nums [ x ] nums [ x 1 ] \textit{nums}[x] \textit{nums}[x 1] nums[x]nums[x1]。
对于下标 x x x可以根据 x x x 的奇偶性以及与 nums [ x ] \textit{nums}[x] nums[x] 相同的元素下标判断只出现一次的元素位于下标 x x x 处、下标 x x x 的左边或下标 x x x 的右边。因此可以使用二分查找得到只出现一次的元素的下标。
用 low \textit{low} low 和 high \textit{high} high 分别表示二分查找的下标范围的下界和上界初始时 low \textit{low} low 和 high \textit{high} high 分别为数组的最小下标和最大下标。每次查找时取 mid \textit{mid} mid 为 low \textit{low} low 和 high \textit{high} high 的平均数向下取整执行如下操作。 如果 mid \textit{mid} mid 是偶数且 nums [ mid ] nums [ mid 1 ] \textit{nums}[\textit{mid}] \textit{nums}[\textit{mid} 1] nums[mid]nums[mid1]或 mid \textit{mid} mid 是奇数且 nums [ mid ] nums [ mid − 1 ] \textit{nums}[\textit{mid}] \textit{nums}[\textit{mid} - 1] nums[mid]nums[mid−1]则只出现一次的元素位于下标 mid \textit{mid} mid 的右边因此在下标范围 [ mid 1 , high ] [\textit{mid} 1, \textit{high}] [mid1,high] 中继续查找。 否则只出现一次的元素位于下标 mid \textit{mid} mid 或其左边因此在下标范围 [ low , mid ] [\textit{low}, \textit{mid}] [low,mid] 中继续查找。
当 low high \textit{low} \textit{high} lowhigh 时查找结束此时 low \textit{low} low 即为只出现一次的元素的下标 nums [ low ] \textit{nums}[\textit{low}] nums[low] 即为只出现一次的元素。
代码
class Solution {public int singleNonDuplicate(int[] nums) {int low 0, high nums.length - 1;while (low high) {int mid low (high - low) / 2;if (mid % 2 0 nums[mid] nums[mid 1] || mid % 2 1 nums[mid] nums[mid - 1]) {low mid 1;} else {high mid;}}return nums[low];}
}复杂度分析 时间复杂度 O ( log n ) O(\log n) O(logn)其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的范围是数组的全部 n n n 个下标二分查找的时间复杂度是 O ( log n ) O(\log n) O(logn)。 空间复杂度 O ( 1 ) O(1) O(1)。
解法二
思路和算法
由于只出现一次的元素的左边有偶数个元素因此只出现一次的元素一定位于偶数下标可以只在偶数下标中二分查找。
由于给定的数组长度是奇数因此数组的最小下标和最大下标都是偶数二分查找的下标范围的下界和上界的初始值分别为数组的最小下标和最大下标。每次查找时取 mid \textit{mid} mid 为 low \textit{low} low 和 high \textit{high} high 的平均数向下取整如果得到的 mid \textit{mid} mid 是奇数则将 mid \textit{mid} mid 减 1 1 1确保 mid \textit{mid} mid 是偶数执行如下操作。 如果 nums [ mid ] nums [ mid 1 ] \textit{nums}[\textit{mid}] \textit{nums}[\textit{mid} 1] nums[mid]nums[mid1]则只出现一次的元素位于下标 mid \textit{mid} mid 的右边因此在下标范围 [ mid 2 , high ] [\textit{mid} 2, \textit{high}] [mid2,high] 中继续查找。 否则只出现一次的元素位于下标 mid \textit{mid} mid 或其左边因此在下标范围 [ low , mid ] [\textit{low}, \textit{mid}] [low,mid] 中继续查找。
二分查找过程中每次更新后的下标范围的下界和上界都是偶数确保只在偶数下标中二分查找。
当 low high \textit{low} \textit{high} lowhigh 时查找结束此时 low \textit{low} low 即为只出现一次的元素的下标 nums [ low ] \textit{nums}[\textit{low}] nums[low] 即为只出现一次的元素。
代码
class Solution {public int singleNonDuplicate(int[] nums) {int low 0, high nums.length - 1;while (low high) {int mid low (high - low) / 2;if (mid % 2 ! 0) {mid--;}if (nums[mid] nums[mid 1]) {low mid 2;} else {high mid;}}return nums[low];}
}复杂度分析 时间复杂度 O ( log n ) O(\log n) O(logn)其中 n n n 是数组 nums \textit{nums} nums 的长度。二分查找的范围是数组的 n 1 2 \dfrac{n 1}{2} 2n1 个偶数下标二分查找的时间复杂度是 O ( log n ) O(\log n) O(logn)。 空间复杂度 O ( 1 ) O(1) O(1)。
