时间O(1)空间)
问题描述
小U最近在学习数组操作，他遇到了一个有趣的问题：给定一个已按非递减顺序排列的整数数组nums，其中除了一个元素只出现一次外，其他所有元素都恰好出现两次，并且相同元素总是相邻出现。小U需要设计一个算法，在 O(log n) 时间复杂度内找到这个只出现一次的元素，并且只能使用常数额外空间。你能帮助小U解决这个问题吗？
要求：
- 算法的时间复杂度必须为 O(log n)，其中 n 是数组
nums的长度。 - 只能使用常数额外空间，不能使用线性扫描或哈希表等需要额外 O(n) 空间的方法。
测试样例
样例1：
输入：
nums = [1, 1, 2, 3, 3, 4, 4, 8, 8]输出：2解释：数字 2 只出现一次，其余数字都恰好出现两次且相邻出现。
样例2：
输入：
nums = [3, 3, 7, 7, 10, 11, 11]输出：10解释：10 是数组中唯一一个不重复的数字，其他数字都成对相邻出现。
样例3：
输入：
nums = [1, 1, 2, 2, 3, 4, 4]输出：3解释：数字 3 只出现一次，是独特的元素，其他数字都成对相邻出现。
约束条件
- 1 ≤ nums.length ≤ 10^5
- 0 ≤ nums[i] ≤ 10^5
- 数组
nums已按非递减顺序排序 - 除了一个元素只出现一次外，其他所有元素都恰好出现两次
- 相同元素总是相邻出现（即数组的排列模式为：[a, a, b, b, c, c, ..., x, ...]）
- 数组长度一定是奇数（因为 2n + 1）
程序代码
#include <stdio.h>
int singleNonDuplicate(int* nums, int numsSize) {
int left = 0, right = numsSize - 1;
while (left < right) {
int mid = left + (right - left) / 2;
// 保证 mid 在偶数位置，便于与下一个比较
if (mid % 2 == 1) {
mid--;
}
// 如果 mid 和 mid+1 相等，说明成对正常，独特元素在右侧
if (nums[mid] == nums[mid + 1]) {
left = mid + 2;
} else {
// 否则独特元素在左侧（包含 mid）
right = mid;
}
}
return nums[left];
}
int main() {
int nums1[] = {1, 1, 2, 3, 3, 4, 4, 8, 8};
int nums2[] = {3, 3, 7, 7, 10, 11, 11};
int nums3[] = {1, 1, 2, 2, 3, 4, 4};
printf("%d\n", singleNonDuplicate(nums1, 9));
printf("%d\n", singleNonDuplicate(nums2, 7));
printf("%d\n", singleNonDuplicate(nums3, 7));
return 0;
}
#include <stdio.h> int singleNonDuplicate(int* nums, int numsSize) { int left = 0, right = numsSize - 1; while (left < right) { int mid = left + (right - left) / 2; // 保证 mid 在偶数位置，便于与下一个比较 if (mid % 2 == 1) { mid--; } // 如果 mid 和 mid+1 相等，说明成对正常，独特元素在右侧 if (nums[mid] == nums[mid + 1]) { left = mid + 2; } else { // 否则独特元素在左侧（包含 mid） right = mid; } } return nums[left]; } int main() { int nums1[] = {1, 1, 2, 3, 3, 4, 4, 8, 8}; int nums2[] = {3, 3, 7, 7, 10, 11, 11}; int nums3[] = {1, 1, 2, 2, 3, 4, 4}; printf("%d\n", singleNonDuplicate(nums1, 9)); printf("%d\n", singleNonDuplicate(nums2, 7)); printf("%d\n", singleNonDuplicate(nums3, 7)); return 0; }
