文章目录
URL题目分析源码源码概述小结 URL
链接：https://leetcode-cn.com/problems/single-element-in-a-sorted-array/
题目
分析
源码
#include int singleNonDuplicate(int *nums , int nums_size){ int low = 0, high = nums_size - 1; while(low < high){ int mid = (high - low)/2 + low; if (nums[mid] == nums[mid ^ 1]) { // tips low = mid + 1; } else { high = mid; } } return nums[low];}int main(){ int num = 0; int arr1[] = {1,1,2,3,3,4,4,8,8}; int size_arr1 = sizeof(arr1)/sizeof(arr1[0]); printf("arr = "); for (int i = 0;i < size_arr1; i++) printf("%d,",arr1[i]); num = singleNonDuplicate(arr1 , size_arr1); printf("nnum = %dn ",num); int arr2[] = {3,3,7,7,10,11,11}; int size_arr2 = sizeof(arr2)/sizeof(arr2[0]); printf("arr = "); for (int i = 0;i < size_arr2; i++) printf("%d,",arr2[i]); num = singleNonDuplicate(arr2 , size_arr2); printf("nnum = %d n ",num); return 0;}
arr = 1,1,2,3,3,4,4,8,8,num = 2arr = 3,3,7,7,10,11,11,num = 10
源码概述
二分法，判断左右边界，数组有序，得mid为偶数位时，mid + 1 = mid⊕1；mid位奇数位时，mid - 1 = mid⊕1
小结
有序数组，搜索，二分法。
注意按位亦或的操作，数据处理的细节问题，还有一个题目是通过位比较的题目我忘记题号了，那一题我觉得很经典。