在给定的数组中查找缺失的数字

Question

Implement a function which takes an array of numbers from 1 to 10 and returns the numbers from 1 to 10 which are missing. examples input: [5,2,6] output: [1,3,4,7,8,9,10]

上述方法的C++程序：

#include <bits/stdc++.h> 

using namespace std; 
 
// Function to find the missing elements 

void printMissingElements(int arr[], int N) 
{ 
 

    // Initialize diff 

    int diff = arr[0] - 0; 
 

    for (int i = 0; i < N; i++) { 
 

        // Check if diff and arr[i]-i 

        // both are equal or not 

        if (arr[i] - i != diff) { 
 

            // Loop for consecutive 

            // missing elements 

            while (diff < arr[i] - i) { 

                cout << i + diff << " "; 

                diff++; 

            } 

        } 

    } 
}

Driver代码

int main() 
{ 

    // Given array arr[] 

    int arr[] = { 5,2,6 }; 
 

    int N = sizeof(arr) / sizeof(int); 
 

    // Function Call 

    printMissingElements(arr, N); 

    return 0; 
}

对于给定的输入如何解决这个问题？

Answer 1

首先“plzz”不是英文世界。其次，问题已经存在了，没必要一直在评论里写“如果有人知道就帮帮我”。然后学习标准headers：Why should I not #include <bits/stdc++.h>? 然后学习Why is "using namespace std;" considered bad practice?

然后阅读问题的文本：“实现一个函数，它接受一个从 1 到 10 的数字数组，returns 缺少从 1 到 10 的数字。示例输入：[5, 2,6] 输出：[1,3,4,7,8,9,10]"

您需要“return 缺少的 1 到 10 的数字。” 我建议您真正使用 C++ 并将 std::vector 放入您的工具箱。然后您可以利用算法，std::find 已为您准备就绪。

#include <algorithm>
#include <iostream>
#include <iterator>
#include <vector>
 
std::vector<int> missingElements(const std::vector<int> v) 
{ 
    std::vector<int> missing;
    for (int i = 1; i <= 10; ++i) {
        if (find(v.begin(), v.end(), i) == v.end()) {
            missing.push_back(i);
        }
    }
    return missing;
}
 
int main() 
{
    std::vector<int> arr = { 5, 2, 6 }; 
    std::vector<int> m = missingElements(arr); 
    copy(m.begin(), m.end(), std::ostream_iterator<int>(std::cout, " "));
    std::cout << "\n";
 
    return 0; 
}

如果你想做一些计算复杂度较低的事情，你可以有一个已经填充的向量，然后标记为删除找到的元素。然后是学习 erase–remove idiom:

的好机会

std::vector<int> missingElements(const std::vector<int> v) 
{ 
    std::vector<int> m = { -1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
    for (const auto& x: v) {
        m[x] = -1;
    }
    m.erase(remove(m.begin(), m.end(), -1), m.end());
    return m;
}

Answer 2

通过这种方法，我们使用 space 来减少执行时间。这里的时间复杂度是 O(N)，其中 N 是数组中给定元素的数量，space 复杂度是 O(1)，即 10' .

 #include<iostream>


void printMissingElements(int arr[], int n){
   
    // Using 1D dp to solve this
   
    int dp[11] = {0};
    for(int i = 0; i < n; i++){
        dp[arr[i]] = 1;
    }
   
    // Traverse through dp list and check for
    // non set indexes
    for(int i = 1; i <= 10; i++){
        if (dp[i] != 1) std::cout << i << " ";
    }
}

int main() {
    int arr[] = {5,2,6};
    int n = sizeof(arr) / sizeof(int);
    printMissingElements(arr, n);
}

Answer 3

    void printMissingElements(int arr[], int n,int low, int high)
{
    bool range[high - low + 1] = { false };

    for (int i = 0; i < n; i++) {
        if (low <= arr[i] && arr[i] <= high)
            range[arr[i] - low] = true;
    }
    for (int x = 0; x <= high - low; x++) {
        if (range[x] == false)
           std:: cout << low + x << " ";
    }
}
int main()
{
    int arr[] = { 5,2,6,6,6,6,8,10 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int low = 1, high = 10;
    printMissingElements(arr, n, low, high);
    return 0;
}

Answer 4

我认为这会起作用：

vector<int> missingnumbers(vector<int> A, int N)
{ vector<int> v;
  for(int i=1;i<=10;i++)
    v.push_back(i);
  sort(A.begin(),A.end());
  int j=0;
  while(j<v.size()) {
  if(binary_search(A.begin(),A.end(),v[j]))
    v.erase(v.begin()+j);
    else
    j++;
  }
 return v;
}

在给定的数组中查找缺失的数字

Find the missing numbers in the given array

c++