LeetCode 540题代码运行异常及末尾语句疑问求助

一、代码错误原因及修复 #

你提供的代码在输入{1,2,3,3,4,4,8,8}时输出8而非2，核心问题出在二分查找的方向判断逻辑错误，以及循环结束后的返回逻辑不严谨：

错误分析 #

1. 二分条件逻辑颠倒：
   对于有序数组中成对出现的元素，单个元素左侧的偶数索引i应满足nums[i] == nums[i+1]，右侧的偶数索引i应满足nums[i] == nums[i-1]。原代码中对偶数/奇数索引的判断逻辑完全搞反，导致搜索范围错误收缩，最终错过正确元素。
2. 循环结束后返回逻辑错误：
   循环结束时left和right是相邻索引，此时需要判断两者对应的元素哪个是单个元素，而非直接返回数组首元素或尾元素。

修复后的代码 #

public class Main {
    public static void main(String[] args) {
        int[] n = {1,2,3,3,4,4,8,8};
        int ans = singleNonDuplicate(n);
        System.out.println(ans); // 输出2
    }

    private static int singleNonDuplicate(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int mid = left + (right - left) / 2;
            // 确保mid是偶数，统一判断逻辑
            if (mid % 2 == 1) {
                mid--;
            }
            // 偶数索引mid的元素与mid+1相等，说明单个元素在右侧
            if (nums[mid] == nums[mid + 1]) {
                left = mid + 2;
            } else {
                // 不相等，说明单个元素在左侧或就是mid
                right = mid;
            }
        }
        // 循环结束时left==right，即为单个元素的索引
        return nums[left];
    }
}

若要保留原循环结构，可修正判断逻辑如下：

private static int singleNonDuplicate(int[] nums) {
    int left = 0;
    int right = nums.length - 1;

    while (left + 1 < right) {
        int mid = (left + right) / 2;
        int num = nums[mid];
        // 先判断mid是否为单个元素
        if (num != nums[mid - 1] && num != nums[mid + 1]) {
            return num;
        }

        if (mid % 2 == 0) {
            // 偶数索引，正常应与mid+1相等，相等则单个元素在右侧
            if (num == nums[mid + 1]) {
                left = mid;
            } else {
                // 不相等，单个元素在左侧
                right = mid;
            }
        } else {
            // 奇数索引，正常应与mid-1相等，相等则单个元素在右侧
            if (num == nums[mid - 1]) {
                left = mid;
            } else {
                // 不相等，单个元素在左侧
                right = mid;
            }
        }
    }

    // 循环结束后判断left和right哪个是单个元素
    if (left == 0) {
        return nums[left];
    }
    return nums[left] == nums[left - 1] ? nums[right] : nums[left];
}

二、原代码末尾if (left == 0) return nums[0]语句的作用 #

原代码中这条语句是试图处理单个元素位于数组第一个位置的情况，比如输入{1,2,2,3,3}：

• 循环结束时left会停在0，right停在1，此时直接返回nums[0]就能得到正确结果。
  但由于原代码的二分逻辑错误，这条语句无法覆盖所有场景，反而在你的测试用例中导致错误判断。

正确场景下，当单个元素在数组开头时，循环结束后left为0，此时nums[0]必然不等于nums[1]，返回它是合理的，但原代码的整体逻辑缺陷让这条语句的作用无法正常发挥。

内容的提问来源于stack exchange，提问作者user19482128