在C ++中查找范围的缺失元素

2024-02-21 17:37:05 163

在这个问题中，我们得到了一个大小为n的数组arr[]以及表示范围的开始和结束元素。我们的任务是查找范围的缺失元素。

问题描述-我们将查找范围中不存在的范围元素。

让我们举个例子来了解这个问题，

输入

arr[] = {4, 6, 3, 7}, start = 3, end = 8

输出结果

5, 8

解释

范围是[3、4、5、6、7、8]

数组为{4，6，3，7}

数组中不存在的范围元素为5、8

解决方法

您可以通过多种方式解决此问题。他们是，

＃方法1

一种简单的解决方法是直接检查数组中范围的所有元素。为此，我们将对数组进行排序，然后在数组中找到范围的第一个元素，然后查找并打印缺少的元素。

该程序说明了我们解决方案的工作原理，

示例

#include 
using namespace std;
void findMissingElements(int arr[], int n, int low, int high){
   sort(arr, arr + n);
   int* pointerVal = lower_bound(arr, arr + n, low);
   int index = pointerVal - arr;
   int i = index, x = low;
   while (i < n && x <= high) {
      if (arr[i] != x)
         cout << x << " ";
      else
         i++;
         x++;
   }
   while (x <= high)
      cout<输出结果缺少的元素是 5 8 9
＃方法2
解决该问题的另一种方法是使用数组。我们将创建一个大小为布尔值的数组（结束-开始）。对于此数组的每个元素，我们将发现数组中是否存在（i+start）。如果存在，则标记arr[i]=true，否则标记arr[i]=false。最后，我们将遍历booleanArray并打印所有标记为false的元素。
该程序说明了我们解决方案的工作原理，
示例
#include 
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
   bool boolArray[end - start + 1] = { false };
   for (int i = 0; i < n; i++) {
      if (start <= arr[i] && arr[i] <= end)
      boolArray[arr[i] - start] = true;
   }
   for (int i = 0; i <= end - start; i++) {
      if (boolArray[i] == false)
         cout<<(start + i)<<"\t";
   }
}
int main(){
   int arr[] = { 4, 6, 3, 7 };
   int n = sizeof(arr) / sizeof(arr[0]);
   int low = 3, high = 9;
   cout<<"缺少的元素是 ";
   findMissingElements(arr, n, low, high);
   return 0;
}
输出结果缺少的元素是 5 8 9
＃方法3
解决该问题的另一种方法是使用哈希表。将数组的所有元素插入哈希表，并在插入后遍历范围并打印范围中不存在的所有元素。
该程序说明了我们解决方案的工作原理，
示例
#include 
using namespace std;
void findMissingElements(int arr[], int n, int start, int end){
   unordered_set arrEle;
   for (int i = 0; i < n; i++)
      arrEle.insert(arr[i]);
   for (int i = start; i <= end; i++)
      if (arrEle.find(i) == arrEle.end())
         cout<输出结果缺少的元素是 5 8 9

在C ++中查找范围的缺失元素

输入

解释

解决方法

＃方法1

示例

＃方法2

示例

＃方法3

示例

热门推荐

随机推荐