题解 | #牛群编号统计#

• 使用二分查找的思想来寻找唯一的非重复元素。
  

• 初始化左边界l为0，右边界r为数组长度减1。
  

• 当l小于r时，循环进行二分查找。
  

• 计算中间位置的索引mid，使用位运算(l + r) >> 1可以提高计算效率。
  

• 根据右半部分的长度m来判断非重复元素的位置。
  

• 如果m为奇数，则非重复元素在右半部分，需要判断mid位置与mid + 1位置的元素是否相等，如果相等，则更新左边界l为mid + 2，否则更新右边界r为mid - 2。如果mid位置的元素与相邻元素都不相等，则找到了非重复元素，直接返回。
  

• 如果m为偶数，则非重复元素在左半部分，需要判断mid位置与mid + 1位置的元素是否相等，如果相等，则更新右边界r为mid - 1，否则更新左边界l为mid + 1。如果mid位置的元素与相邻元素都不相等，则找到了非重复元素，直接返回。
  

• 当循环结束时，左边界l和右边界r相等，返回该位置上的元素作为唯一的非重复元素。
  

class Solution {
  public:
    /**
     * 找出数组中唯一的一个非重复元素
     * @param nums 存储整型元素的数组
     * @return 返回唯一的非重复元素
     */
    int singleNonDuplicate(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = (l + r) >> 1; // 计算中间位置的索引
            int m = (r - l + 2) >> 1; // 计算右半部分的长度
            if (m & 1) { // 如果右半部分长度为奇数
                if (nums[mid] == nums[mid + 1]) {
                    l = mid + 2; // 非重复元素在右半部分，更新左边界的位置
                } else if (nums[mid] == nums[mid - 1]) {
                    r = mid - 2; // 非重复元素在左半部分，更新右边界的位置
                } else if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
                    return nums[mid]; // 找到非重复元素，直接返回
                }
            } else { // 如果右半部分长度为偶数
                if (nums[mid] == nums[mid + 1]) {
                    r = mid - 1; // 非重复元素在左半部分，更新右边界的位置
                } else if (nums[mid] == nums[mid - 1]) {
                    l = mid + 1; // 非重复元素在右半部分，更新左边界的位置
                } else if (nums[mid] != nums[mid - 1] && nums[mid] != nums[mid + 1]) {
                    return nums[mid]; // 找到非重复元素，直接返回
                }
            }
        }
        return nums[l]; // 当循环结束时，左边界和右边界相等，返回该位置上的元素
    }
};