数据结构
网络
关系数据库管理系统 (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 次浏览
广告