資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究使用C++查詢大小為n的有序陣列中唯一重複的元素
在這個問題中，我們得到一個大小為N的陣列arr[]，其中包含從1到N-1的值，陣列中有一個值出現兩次。我們的任務是_查詢大小為n的有序陣列中唯一重複的元素_。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {1, 2, 3, 4, 5, 5, 6, 7}輸出
5
解決方案
解決這個問題的一個簡單方法是使用線性搜尋，並檢查arr[i]和arr[i+1]的值是否相同。在這種情況下，返回arr[i]，即重複的值。
示例1
程式演示了我們解決方案的工作原理
#include <iostream>
using namespace std;
int findRepeatingValueArr(int arr[], int N){
for(int i = 0; i < N; i++){
if(arr[i] == arr[i+1])
return (arr[i]);
}
return -1;
}
int main(){
int arr[] = {1, 2, 3, 4, 4, 5, 6};
int N = sizeof(arr)/sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, N);
return 0;
}輸出
The repeating value in the array is 4
解決這個問題的另一種方法是使用二分查詢演算法來查詢在中間索引處出現兩次的元素。如果中間索引值重複，則列印它。如果它不在索引位置，則遍歷右子陣列，否則遍歷左子陣列。
示例2
程式演示了我們解決方案的工作原理
#include <bits/stdc++.h>
using namespace std;
int findRepeatingValueArr(int arr[], int s, int e){
if (s > e)
return -1;
int mid = (s + e) / 2;
if (arr[mid] != mid + 1){
if (mid > 0 && arr[mid]==arr[mid-1])
return arr[mid];
return arr[findRepeatingValueArr(arr, s, mid-1)];
}
return arr[findRepeatingValueArr(arr, mid+1, e)];
}
int main(){
int arr[] = {1, 2, 3, 4, 5, 6, 6, 7, 8, 9};
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repeating value in the array is "<<findRepeatingValueArr(arr, 0, n-1);;
return 0;
}輸出
The repeating value in the array is 6
更新於：2022年2月11日
198 次瀏覽
廣告