資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 查詢 1 到 n-1 之間唯一的重複元素
在這個問題中，我們得到一個大小為 N 的無序陣列 arr[]，其中包含從 1 到 N-1 的值，並且陣列中有一個值出現了兩次。我們的任務是*查詢 1 到 n-1 之間唯一的重複元素*。
讓我們舉個例子來理解這個問題：
輸入
arr[] = {3, 5, 4, 1, 2, 1}輸出
1
解決方案方法
解決此問題的一個簡單方法是遍歷陣列，並對每個值查詢該元素是否在陣列中的其他位置存在。返回出現兩次的值。
示例 1
程式說明了解決方案的工作原理
#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)
if(arr[i] == arr[j])
return arr[i];
}
int main(){
int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
return 0;
}輸出
The repetitive value in the array is 6
解決此問題的另一種方法是利用以下事實：可以透過從 1 到 (N-1) 所有整數的和中減去陣列和來找到陣列中重複的值。
前 N-1 個自然數之和 (Sn) = n*(n-1)/2
doubleVal = arrSum - (Sn)
示例 2
程式說明了解決方案的工作原理
#include <iostream>
using namespace std;
int findRepValArr(int arr[], int n){
int arrSum = 0;
for(int i = 0; i < n; i++)
arrSum += arr[i];
int sn = (((n)*(n-1))/2);
return arrSum - sn;
}
int main(){
int arr[] = { 5, 3, 2, 6, 6, 1, 4 };
int n = sizeof(arr) / sizeof(arr[0]);
cout<<"The repetitive value in the array is "<<findRepValArr(arr, n);
return 0;
}輸出
The repetitive value in the array is 6
更新於: 2022年2月11日
141 次檢視
廣告