数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济
心理学
社会研究
时尚研究
法律研究使用 C++ 求数组中阶乘和
考虑我们有一个已排序数组 A，其中重复出现所有元素两次，但只有一个元素仅出现一次。我们要找出现在的这个元素。如果数组是 [1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9]，那么单独出现的元素是 5。
我们使用二分查找来解决这个问题。单个元素出现前的所有元素在索引 0, 2, 4, … 处第一次出现，在索引 1, 3, 5, … 处第二次出现，但在单个元素之后，第一个元素的所有出现都在奇索引，第二个元素在偶数索引处。
所以首先找到中间索引 mid，如果 mid 是偶数，然后比较 A[mid] 与 A[mid + 1]，如果两者相同，则根据需要向左或向右移动。否则，当 mid 为奇数时，比较 A[mid] 与 A[mid – 1]，如果它们相同，则根据需要向左或向右移动。
示例
#include<iostream>
using namespace std;
void findSingleElement(int *arr, int left, int right) {
if (left > right)
return;
if (left==right) {
cout << "The required element is: "<< arr[left];
return;
}
int mid = (left + right) / 2;
if (mid%2 == 0) {
if (arr[mid] == arr[mid+1])
findSingleElement(arr, mid+2, right);
else
findSingleElement(arr, left, mid);
}else{
if (arr[mid] == arr[mid-1])
findSingleElement(arr, mid+1, right);
else
findSingleElement(arr, left, mid-1);
}
}
int main() {
int arr[] = {1, 1, 3, 3, 4, 4, 5, 6, 6, 7, 7, 9, 9};
int len = sizeof(arr)/sizeof(arr[0]);
findSingleElement(arr, 0, len-1);
}输出
The required element is: 5
更新日期： 2019-11-04
175 次查看
广告