540. 有序数组中的单一元素

题目链接：https://leetcode.cn/problems/single-element-in-a-sorted-array/description/思路题目中要求了复杂度为$O(\log N)$，所以不能用线性扫描的方法，还是只能用二分法。其实刚拿到这题是没什么思路的，但看了一下题解的提示，知道了因为这个单独元素的插入，会破坏原始的元素重复的规律：在没有这个单独的元素前，始终是偶数位=奇数位，如此重复下去，比如[1,1,3,3,5,5]，其中每组两个重复元素11，33，55，对应的索引分别为01，23，45，都是左边为偶数索引，右边为奇数索引但是在插入了这个单独的元素后，这种规律被打破，比如[1,1,2,3,3,5,5]，这样一来，每组两个重复元素对应索引就变成了01，34，56，可以发现，在这个单独元素的左边，规律还是保持不变，左边为偶右边为奇，但在这个元素的右边，就变成了每组左边索引为奇，右边为偶可以利用这个规律来进行求解，梳理一下就是：假设mid落在单独元素的左边：如果mid为奇数，那么一定满足nums[mid] == nums[mid - 1]如果mid为偶数，那么一

默认分类 · 05-24