資料結構
網路
關係資料庫管理系統
作業系統
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 次檢視
廣告