问题描述小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^50 ≤ nums[i] ≤ 10^5数组nums已按非递减顺序排序除了一个元素只出现一次外其他所有元素都恰好出现两次相同元素总是相邻出现即数组的排列模式为[a, a, b, b, c, c, ..., x, ...]数组长度一定是奇数因为 2n 1程序代码#include stdio.hint 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 和 mid1 相等说明成对正常独特元素在右侧if (nums[mid] nums[mid 1]) {left mid 2;} else {// 否则独特元素在左侧包含 midright 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 和 mid1 相等说明成对正常独特元素在右侧 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; }运行结果