資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在C++中查詢重複陣列中丟失的元素
概念
給定兩個陣列，它們互為副本，只有一個元素除外，這意味著一個數組中缺少一個元素，我們的任務是確定該丟失的元素。
輸入
arr1[] = {2, 5, 6, 8, 10}
arr2[] = {5, 6, 8, 10}輸出
2
第二個陣列缺少2。
輸入
arr1[] = {3, 4, 5, 6}
arr2[] = {3, 4, 5, 6, 7}輸出
7
第一個陣列缺少7。
方法
在這裡，我們採用一個簡單的解決方案，我們遍歷陣列並逐個元素進行驗證，並在檢測到不匹配時標記丟失的元素。但是，此解決方案的缺點是它需要線性時間才能遍歷陣列。
我們可以實現另一個基於二分查詢方法的高效解決方案。我們遵循以下逐步解釋的演算法：
- 在較大的陣列中開始二分查詢，並將中間值設定為 (low + high) / 2
- 如果兩個陣列的值相同，則丟失的元素必須在右側，因此將low設定為mid
- 否則，將high設定為mid，因為如果中間元素不同，則丟失的元素必須在較大陣列的左側。
- 我們必須分別處理特殊情況，因為對於單元素和零元素陣列，單元素本身就是丟失的元素。
如果第一個元素本身不相等，則該元素將是丟失的元素。
示例
// C++ program to find missing element from same
// arrays (except one missing element)
#include <bits/stdc++.h>
using namespace std;
// Shows function to determine missing element based on binary
// search approach. arrA[] is of larger size and
// Q is size of it. arrA[] and arrB[] are assumed
// to be in same order.
int findMissingUtil(int arrA[], int arrB[], int Q){
// Considers special case, for only element which is
// missing in second array
if (Q == 1)
return arrA[0];
// Considers special case, for first element missing
if (arrA[0] != arrB[0])
return arrA[0];
// Used to initialize current corner points
int low = 0, high = Q - 1;
// Iterate until low < high
while (low < high){
int mid = (low + high) / 2;
// It has been observed that if element at mid indices are equal
// then go to right subarray
if (arrA[mid] == arrB[mid])
low = mid;
else
high = mid;
// So if low, high becomes contiguous, break
if (low == high - 1)
break;
}
// Now missing element will be at high index of
// bigger array
return arrA[high];
}
// So this function mainly does basic error checking
// and calls findMissingUtil
void findMissing(int arrA[], int arrB[], int P, int Q){
if (Q == P-1)
cout << "Missing Element is "
<< findMissingUtil(arrA, arrB, P) << endl;
else if (P == Q-1)
cout << "Missing Element is "
<< findMissingUtil(arrB, arrA, Q) << endl;
else
cout << "Invalid Input";
}
// Driver Code
int main(){
int arrA[] = {2, 5, 6, 8, 10};
int arrB[] = {5, 6, 8, 10};
int P = sizeof(arrA) / sizeof(int);
int Q = sizeof(arrB) / sizeof(int);
findMissing(arrA, arrB, P, Q);
return 0;
}輸出
Missing Element is 2
更新於：2020年7月24日
101 次檢視
廣告