【数据结构与算法】之有序数组中的单一元素的算法
【摘要】
一、题目要求
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
示例一：
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
12
示例二：
...
一、题目要求
给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。
- 示例一：
输入: [1,1,2,3,3,4,4,8,8]
输出: 2
- 1
- 2
- 示例二：
输入: [3,3,7,7,10,11,11]
输出: 10
- 1
- 2
- 注意: 您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。
二、示例算法
① 暴力法：线性搜索
- 可以使用线性搜索来检查数组中的每个元素，直到找到单个元素。
- 算法：
- 从第一个元素开始，检查每个第二个元素是否与当前元素相同。如果不同，说明该元素是单个元素。
- 如果到达最后一个元素，则它为单一元素。
- Java 实现
class Solution {
public int singleNonDuplicate(int[] nums) {
for (int i = 0; i < nums.length - 1; i+=2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums[nums.length - 1];
}}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- Python 实现
def singleNonDuplicate(self, nums: List[int]) -> int:
for i in range(0, len(nums) - 2, 2):
if nums[i] != nums[i + 1]:
return nums[i]
return nums[-1]
- 1
- 2
- 3
- 4
- 5
- C++ 实现
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
for (int i = 0; i < nums.size() - 1; i += 2) {
if (nums[i] != nums[i + 1]) {
return nums[i];
}
}
return nums.back();
}};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 复杂度分析
- 时间复杂度：O(n)。我们的线性搜索只查看每个元素一次。
- 空间复杂度：O(1)，只使用了常数的额外空间。
- 尽管这个解决方案可行，但是问题中要求使用时间复杂度在 O(log n) 的解决方案。因此，该解决方案还不够好。
② 二分搜索
- 将线性搜索转换为二分搜索是有意义的，它能加快效率。为了使用二分搜索，需要查看中间的元素来判断我们的答案在中间，左边还是右边。我数组个数始终是奇数，因为有一个元素出现一次，其余元素出现两次。
- 当从中心移除一对元素时发生的情况，剩下左子数组和右子数组：
-
与原数组一样，包含单个元素的子数组元素个数必为奇数，不包含单个元素的子数组必为偶数。因此，当原数组移除一对元素后，然后计算出哪一侧的子数组元素个数是奇数，这样我们就能够知道下一步应该在哪一侧进行搜索。
-
算法：
- 我们首先将 lo 和 hi 指向数组首尾两个元素。然后进行二分搜索将数组搜索空间减半，直到找到单一元素或者仅剩一个元素为止。当搜索空间只剩一个元素，则该元素就是单个元素。
- 在每个循环迭代中，我们确定 mid，变量 halvesAreEven = (hi - mid) % 2== 0。通过查看中间元素同一元素为哪一个（左侧子数组中的最后一个元素或右侧子数组中的第一个元素），我们可以通过变量 halvesAreEven 确定现在哪一侧元素个数为奇数，并更新 lo 和 hi。
- 最难的部分是根据 mid 和 halvesAreEven 的值正确更新 lo 和 hi。我们通过下图来帮助我们理解。
-
中间元素的同一元素在右边，且被 mid 分成两半的数组为偶数。
将右子数组的第一个元素移除后，则右子数组元素个数变成奇数，应将 lo 设置为 mid + 2。
-
中间元素的同一元素在右边，且被 mid 分成两半的数组为奇数。
将右子数组的第一个元素移除后，则右子数组的元素个数变为偶数，应将 hi 设置为 mid - 1。
-
中间元素的同一元素在左边，且被 mid 分成两半的数组为偶数。
将左子数组的最后一个元素移除后，则左子数组的元素个数变为奇数，应将 hi 设置为 mid - 2。
-
中间元素的同一元素在左边，且被 mid 分成两半的数组为奇数。
将左子数组的最后一个元素移除后，则左子数组的元素个数变为偶数，应将 lo 设置为 mid + 1。
-
Java 实现
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
boolean halvesAreEven = (hi - mid) % 2 == 0;
if (nums[mid + 1] == nums[mid]) {
if (halvesAreEven) {
lo = mid + 2;
} else {
hi = mid - 1;
}
} else if (nums[mid - 1] == nums[mid]) {
if (halvesAreEven) {
hi = mid - 2;
} else {
lo = mid + 1;
}
} else {
return nums[mid];
}
}
return nums[lo];
}}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- Python 实现
def singleNonDuplicate(self, nums: List[int]) -> int:
lo = 0
hi = len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
halves_are_even = (hi - mid) % 2 == 0
if nums[mid + 1] == nums[mid]:
if halves_are_even:
lo = mid + 2
else:
hi = mid - 1
elif nums[mid - 1] == nums[mid]:
if halves_are_even:
hi = mid - 2
else:
lo = mid + 1
else:
return nums[mid]
return nums[lo]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- C++ 实现
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0;
int hi = nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
bool halvesAreEven = (hi - mid) % 2 == 0;
if (nums[mid + 1] == nums[mid]) {
if (halvesAreEven) {
lo = mid + 2;
} else {
hi = mid - 1;
}
} else if (nums[mid - 1] == nums[mid]) {
if (halvesAreEven) {
hi = mid - 2;
} else {
lo = mid + 1;
}
} else {
return nums[mid];
}
}
return nums[lo];
}};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 另外，你会发现即使数组没有经过排序，只要将同一元素放在一起，该算法仍然起作用（例：[10, 10, 4, 4, 7, 11, 11, 12, 12, 2, 2]）。他们的顺序无关紧要，重要的是含有单个元素的子数组元素个数为奇数。
- 复杂度分析
- 时间复杂度：O(log n)。在每次循环迭代中，我们将搜索空间减少了一半。
- 空间复杂度：O(1)，仅使用了常数空间。
③ 仅对偶数索引进行二分搜索
- 事实证明我们只需要对偶数索引进行二分搜索。这种方法与方法二都是不错的方法，但是该方法比方法二更加优雅。
- 在该算法中，我们对所有偶数索引进行搜索，直到遇到第一个其后元素不相同的索引。
- 我们可以使用二分搜索替代线性搜索。
- 在单个元素的后面，则成对的元素变为奇数索引后跟他们的同一元素。说明我们在检索单个元素后面的偶数索引时，其后都没有它的同一元素。因此，我们可以通过偶数索引确定单个元素在左侧还是右侧。
- 算法：
- 奇数长度的数组首尾元素索引都为偶数，因此我们可以将 lo 和 hi 设置为数组首尾。
- 我们需要确保 mid 是偶数，如果为奇数，则将其减 1。
- 然后，我们检查 mid 的元素是否与其后面的索引相同。
- 如果相同，则我们知道 mid 不是单个元素。且单个元素在 mid 之后。则我们将lo 设置为 mid + 2。
- 如果不是，则我们知道单个元素位于 mid，或者在 mid 之前。我们将 hi 设置为mid。
一旦 lo == hi，则当前搜索空间为 1 个元素，那么该元素为单个元素，我们将返回它。
- Java 实现
class Solution {
public int singleNonDuplicate(int[] nums) {
int lo = 0;
int hi = nums.length - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- Python 实现
def singleNonDuplicate(self, nums: List[int]) -> int:
lo = 0
hi = len(nums) - 1
while lo < hi:
mid = lo + (hi - lo) // 2
if mid % 2 == 1:
mid -= 1
if nums[mid] == nums[mid + 1]:
lo = mid + 2
else:
hi = mid
return nums[lo]
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- C++ 实现
class Solution {
public:
int singleNonDuplicate(vector<int>& nums) {
int lo = 0;
int hi = nums.size() - 1;
while (lo < hi) {
int mid = lo + (hi - lo) / 2;
if (mid % 2 == 1) mid--;
if (nums[mid] == nums[mid + 1]) {
lo = mid + 2;
} else {
hi = mid;
}
}
return nums[lo];
}};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 复杂度分析
- 时间复杂度：O(log n/2) = O(log n)。我们仅对元素的一半进行二分搜索。
- 空间复杂度：O(1)，仅使用了常数空间。
文章来源: blog.csdn.net，作者：Serendipity·y，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/Forever_wj/article/details/108850759
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）