c - 给定一个整数数组，其中每个元素成对（彼此相邻）出现一个整数，如何找到这个整数？

问题描述

我正在为考试而学习，并通过以下我完全不理解的解决方案发现了这个问题。对他们做了什么以及为什么有任何帮助？

我有一个未排序的数组，其中数组中的每个整数成对出现（彼此相邻）；在这个数组中，只有一个没有一对的整数出现；另外，不能有两对相同的整数相邻！

例如，给定以下数组，我需要在最佳时间（最佳时间复杂度）找到这个奇数：

8 8 5 5 3 6 6 -1 -1 7 7

输出为 3！

编码：

int FindOddOccuring(int arr[], int n) {
    int left = 0, right = n / 2; 

    while (left < right) 
    { 
       int mid = (left + right) / 2; 

       if (arr[2 * mid + 1] == arr[2 * mid]) 
          left = mid + 1; 
       else 
          right = mid; 
    } 
    return arr[2 * right]; 
}

标签： c

关键在于：

if (arr[2 * mid + 1] == arr[2 * mid])

假设数字是成对插入的，并且只能是一个非配对数字，如果您检查数组中前半部分的最后两个数字之间的两个连续并且它们不相等，那么您的反叛数字将不可避免地是在数组的后半部分......为什么？！：因为“反叛”数字是打破 a[i]=a[i+1] 不变量的那个数字，并且您总是从偶数位置签入上一个……我的解释够清楚吗？是不是太琐碎了？我希望它有帮助！

c - 给定一个整数数组，其中每个元素成对（彼此相邻）出现一个整数，如何找到这个整数？

问题描述

解决方案

推荐阅读