【原】LeetCode 540.有序数组中的单一元素

LeetCode 540.有序数组中的单一元素题目链接:

https:///problems/single-element-in-a-sorted-array/

题目描述:

给定一个只包含整数的有序数组，每个元素都会出现两次，唯有一个数只会出现一次，找出这个数。

示例 1：

输入: [1,1,2,3,3,4,4,8,8]

输出: 2

示例 2：

输入: [3,3,7,7,10,11,11]

输出: 10

注意

您的方案应该在 O(log n)时间复杂度和 O(1)空间复杂度中运行。

题目分析:

    读完这道题，最直接的还是用暴力破解法(见题解一)，虽然暴力破解空间复杂度为O(1)，但是时间复杂度为O(n)，不能满足题目要求的O(log n)。所以我们对题解进行改进。

    我们可以使用二分查找法解决此题。首先我们还是按照套路定义出左右边界，当左边界小于右边界执行循环。在循环中我们获取区间的中点，同时，这道题需要我们定义一个标志位，判断单一元素出现在左子区间还是右子区间。以下是各类情况的分析：

情况一：

    和中间元素相同的元素在中间元素的右边，并且左右子区间元素个数都为偶数，在移除中间两个相同的元素后，左子区间元素个数为偶数，右子区间的元素个数为奇数，说明我们要找的单一元素在右子区间。所以，我们让左边界移动到中点元素的右边第二个位置，从而缩小查找区间范围。

情况二：

    和中间元素相同的元素在中间元素的右边，并且左右子区间元素个数都为奇数，在移除中间两个相同的元素后，左子区间元素个数为奇数，右子区间的元素个数为偶数，说明我们要找的单一元素在左子区间。所以，我们让右边界移动到中点元素的左边第一个位置，从而缩小查找区间范围。

情况三：

    和中间元素相同的元素在中间元素的左边，并且左右子区间元素个数都为偶数，在移除中间两个相同的元素后，左子区间元素个数为奇数，右子区间的元素个数为偶数，说明我们要找的单一元素在左子区间。所以，我们让右边界移动到中点元素的左边第二个位置，从而缩小查找区间范围。

情况四：

    和中间元素相同的元素在中间元素的左边，并且左右子区间元素个数都为奇数，在移除中间两个相同的元素后，左子区间元素个数为偶数，右子区间的元素个数为奇数，说明我们要找的单一元素在右子区间。所以，我们让左边界移动到中点元素的右边第一个位置，从而缩小查找区间范围。

情况五：

    中间元素与中间左边的第一个元素和中间右边的第一个元素都互不相同，说明中间元素即为单一元素。

题解一(暴力破解法):

执行用时: 0 ms

内存消耗: 38.5 MB

class Solution {    public int singleNonDuplicate(int[] nums) {        // 从第一个元素开始，检查当前元素和下一个元素是否相同        for (int i = 0; i < nums.length - 1; i+=2)            // 如果不同，则说明当前元素为单一元素            if (nums[i] != nums[i + 1])                // 返回当前元素                return nums[i];        // 如果到最后没有找到元素，说明最后一个元素是单一元素        return nums[nums.length - 1];    }}

题解二(二分查找法):

执行用时: 0 ms

内存消耗: 38.5 MB

class Solution {    public int singleNonDuplicate(int[] nums) {        // 定义左右边界        int left = 0, right = nums.length - 1;        // 当左边界小于右边界执行循环        while (left < right) {            // 获取区间中点            int mid = left + (right - left) / 2;            // 定义标志位判断右子区间元素数量是否为偶数，为偶数则标志位值为真            boolean flag = (right - mid) % 2 == 0;            // 如果中点值与中点下一个元素值相等            if (nums[mid + 1] == nums[mid]) {                // 右子区间元素为偶数个，则让左边界移动到中点右边第二个节点处                if (flag)                    left = mid + 2;                // 右子区间元素为奇数个，则让右边界移动到中点左边第一个节点处                else                    right = mid - 1;            }            // 如果中点值与中点前一个元素值相等            else if (nums[mid - 1] == nums[mid]) {                // 右子区间元素为偶数个，则让右边界移动到中点左边第二个节点处                if (flag)                    right = mid - 2;                // 右子区间元素为奇数个，则让左边界移动到中点右边第一个节点处                else                    left = mid + 1;            }            // 否则 中点值 与 中点前一个元素值 和 中点后一个元素值 都不相等，说明中点值就是单一元素            else                return nums[mid];        }        // 返回单一元素        return nums[left];    }}

题目来源:力扣(LeetCode)