给定一个整数数组，打印0-99范围内缺失的元素。如果丢失了不止一个，请核对，否则只需打印数字。 请注意，输入数组可能无法排序，并且可能包含[0-99]范围之外的数字，但在打印缺少的元素时，仅考虑此范围。
null
例如：
Input: {88, 105, 3, 2, 200, 0, 10}Output: 1 4-9 11-87 89-99Input: {9, 6, 900, 850, 5, 90, 100, 99}Output: 0-4 7-8 10-89 91-98
预期时间复杂度O（n），其中n是输入数组的大小。
其思想是使用大小为100的布尔数组来跟踪0到99之间的数组元素。我们首先遍历输入数组，并在布尔数组中标记这样的当前元素。标记所有当前元素后，布尔数组将用于打印缺少的元素。
以下是上述想法的实施。
C++
// C++ program for print missing elements #include <bits/stdc++.h> #define LIMIT 100 using namespace std; // A O(n) function to print missing elements in an array void printMissing( int arr[], int n) { // Initialize all number from 0 to 99 as NOT seen bool seen[LIMIT] = { false }; // Mark present elements in range [0-99] as seen for ( int i=0; i<n; i++) if (arr[i] < LIMIT) seen[arr[i]] = true ; // Print missing element int i = 0; while (i < LIMIT) { // If i is missing if (seen[i] == false ) { // Find if there are more missing elements after i int j = i+1; while (j < LIMIT && seen[j] == false ) j++; // Print missing single or range (i+1 == j)? cout << i : cout << "" << i << "-" << j-1; // Update u i = j; } else i++; } } // Driver program int main() { int arr[] = {88, 105, 3, 2, 200, 0, 10}; int n = sizeof (arr)/ sizeof (arr[0]); printMissing(arr, n); return 0; } // This code is contributed by shivanisinghss2110 |
C
// C program for print missing elements #include<stdio.h> #define LIMIT 100 // A O(n) function to print missing elements in an array void printMissing( int arr[], int n) { // Initialize all number from 0 to 99 as NOT seen bool seen[LIMIT] = { false }; // Mark present elements in range [0-99] as seen for ( int i=0; i<n; i++) if (arr[i] < LIMIT) seen[arr[i]] = true ; // Print missing element int i = 0; while (i < LIMIT) { // If i is missing if (seen[i] == false ) { // Find if there are more missing elements after i int j = i+1; while (j < LIMIT && seen[j] == false ) j++; // Print missing single or range (i+1 == j)? printf ( "%dn" , i): printf ( "%d-%dn" , i, j-1); // Update u i = j; } else i++; } } // Driver program int main() { int arr[] = {88, 105, 3, 2, 200, 0, 10}; int n = sizeof (arr)/ sizeof (arr[0]); printMissing(arr, n); return 0; } |
JAVA
class PrintMissingElement { // A O(n) function to print missing elements in an array void printMissing( int arr[], int n) { int LIMIT = 100 ; boolean seen[] = new boolean [LIMIT]; // Initialize all number from 0 to 99 as NOT seen for ( int i = 0 ; i < LIMIT; i++) seen[i] = false ; // Mark present elements in range [0-99] as seen for ( int i = 0 ; i < n; i++) { if (arr[i] < LIMIT) seen[arr[i]] = true ; } // Print missing element int i = 0 ; while (i < LIMIT) { // If i is missing if (seen[i] == false ) { // Find if there are more missing elements after i int j = i + 1 ; while (j < LIMIT && seen[j] == false ) j++; // Print missing single or range int p = j- 1 ; System.out.println(i+ 1 ==j ? i : i + "-" + p); // Update u i = j; } else i++; } } // Driver program to test above functions public static void main(String[] args) { PrintMissingElement missing = new PrintMissingElement(); int arr[] = { 88 , 105 , 3 , 2 , 200 , 0 , 10 }; int n = arr.length; missing.printMissing(arr, n); } } |
Python3
# Python3 program for print missing elements # A O(n) function to print missing elements in an array def printMissing(arr, n) : LIMIT = 100 seen = [ False ] * LIMIT # Initialize all number from 0 to 99 as NOT seen for i in range (LIMIT) : seen[i] = False # Mark present elements in range [0-99] as seen for i in range (n) : if (arr[i] < LIMIT) : seen[arr[i]] = True # Print missing element i = 0 while (i < LIMIT) : # If i is missing if (seen[i] = = False ) : # Find if there are more missing elements after i j = i + 1 while (j < LIMIT and seen[j] = = False ) : j + = 1 # Print missing single or range p = j - 1 if (i + 1 = = j) : print (i) else : print (i, "-" , p) # Update u i = j else : i + = 1 # Driver code arr = [ 88 , 105 , 3 , 2 , 200 , 0 , 10 ] n = len (arr) printMissing(arr, n) # This code is contributed by divyesh072019. |
C#
using System; class GFG { // A O(n) function to print missing elements in an array static void printMissing( int [] arr, int n) { int LIMIT = 100; bool [] seen = new bool [LIMIT]; int i; // Initialize all number from 0 to 99 as NOT seen for (i = 0; i < LIMIT; i++) seen[i] = false ; // Mark present elements in range [0-99] as seen for (i = 0; i < n; i++) { if (arr[i] < LIMIT) seen[arr[i]] = true ; } // Print missing element i = 0; while (i < LIMIT) { // If i is missing if (seen[i] == false ) { // Find if there are more missing elements after i int j = i + 1; while (j < LIMIT && seen[j] == false ) j++; // Print missing single or range int p = j - 1; if (i + 1 == j) { Console.WriteLine(i); } else { Console.WriteLine(i + "-" + p); } // Update u i = j; } else i++; } } // Driver code static void Main() { int [] arr = {88, 105, 3, 2, 200, 0, 10}; int n = arr.Length; printMissing(arr, n); } } // This code is contributed by divyeshrabadiya07. |
PHP
<?php // PHP program for print // missing elements $LIMIT = 100; // A O(n) function to print // missing elements in an array function printMissing( $arr , $n ) { global $LIMIT ; // Initialize all number from // 0 to 99 as NOT seen $seen = (false); // Mark present elements in. // range [0-99] as seen for ( $i = 0; $i < $n ; $i ++) if ( $arr [ $i ] < $LIMIT ) $seen [ $arr [ $i ]] = true; // Print missing element $i = 0; while ( $i < $LIMIT ) { // If i is missing if ( $seen [ $i ] == false) { // Find if there are more // missing elements after i $j = $i + 1; while ( $j < $LIMIT && $seen [ $j ] == false) $j ++; // Print missing // single or range if (( $i + 1 == $j ) == true) echo $i , "" ; else echo $i , "-" , $j - 1, "" ; // Update u $i = $j ; } else $i ++; } } // Driver Code $arr = array (88, 105, 3, 2, 200, 0, 10); $n = sizeof( $arr ); printMissing( $arr , $n ); // This code is contributed by aj_36 ?> |
Javascript
<script> // Javascript program for print missing elements // A O(n) function to print missing // elements in an array function printMissing(arr, n) { let LIMIT = 100; let seen = new Array(LIMIT); let i; // Initialize all number from // 0 to 99 as NOT seen for (i = 0; i < LIMIT; i++) seen[i] = false ; // Mark present elements in // range [0-99] as seen for (i = 0; i < n; i++) { if (arr[i] < LIMIT) seen[arr[i]] = true ; } // Print missing element i = 0; while (i < LIMIT) { // If i is missing if (seen[i] == false ) { // Find if there are more missing // elements after i let j = i + 1; while (j < LIMIT && seen[j] == false ) j++; // Print missing single or range let p = j - 1; if (i + 1 == j) { document.write(i + "</br>" ); } else { document.write(i + "-" + p + "</br>" ); } // Update u i = j; } else i++; } } // Driver code let arr = [88, 105, 3, 2, 200, 0, 10]; let n = arr.length; printMissing(arr, n); // This code is contributed by suresh07 </script> |
输出：
14-911-8789-99
上述程序的时间复杂度为O（n）。
本文由 维涅什·纳拉亚南 和 索米亚·桑帕斯 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
