给定一个大小为N的数组，设A和B分别为数组中的最小值和最大值。任务是找出应该向给定数组中添加多少个数字，以便[A，B]范围内的所有元素在数组中至少出现一次。 例如：
null
Input : arr[] = {4, 5, 3, 8, 6}Output : 1Only 7 to be added in the list.Input : arr[] = {2, 1, 3}Output : 0
方法1（排序） 1-对数组进行排序。 2-比较arr[i]==arr[i+1]-1与否。如果没有，更新计数=arr[i+1]-arr[i]-1。 3-返回计数。
C++
// C++ program for above implementation #include <bits/stdc++.h> using namespace std; // Function to count numbers to be added int countNum( int arr[], int n) { int count = 0; // Sort the array sort(arr, arr + n); // Check if elements are consecutive // or not. If not, update count for ( int i = 0; i < n - 1; i++) if (arr[i] != arr[i+1] && arr[i] != arr[i + 1] - 1) count += arr[i + 1] - arr[i] - 1; return count; } // Drivers code int main() { int arr[] = { 3, 5, 8, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countNum(arr, n) << endl; return 0; } |
JAVA
// java program for above implementation import java.io.*; import java.util.*; public class GFG { // Function to count numbers to be added static int countNum( int []arr, int n) { int count = 0 ; // Sort the array Arrays.sort(arr); // Check if elements are consecutive // or not. If not, update count for ( int i = 0 ; i < n - 1 ; i++) if (arr[i] != arr[i+ 1 ] && arr[i] != arr[i + 1 ] - 1 ) count += arr[i + 1 ] - arr[i] - 1 ; return count; } // Drivers code static public void main (String[] args) { int []arr = { 3 , 5 , 8 , 6 }; int n = arr.length; System.out.println(countNum(arr, n)); } } // This code is contributed by vt_m. |
Python3
# python program for above implementation # Function to count numbers to be added def countNum(arr, n): count = 0 # Sort the array arr.sort() # Check if elements are consecutive # or not. If not, update count for i in range ( 0 , n - 1 ): if (arr[i] ! = arr[i + 1 ] and arr[i] ! = arr[i + 1 ] - 1 ): count + = arr[i + 1 ] - arr[i] - 1 ; return count # Drivers code arr = [ 3 , 5 , 8 , 6 ] n = len (arr) print (countNum(arr, n)) # This code is contributed by Sam007 |
C#
// C# program for above implementation using System; public class GFG { // Function to count numbers to be added static int countNum( int []arr, int n) { int count = 0; // Sort the array Array.Sort(arr); // Check if elements are consecutive // or not. If not, update count for ( int i = 0; i < n - 1; i++) if (arr[i] != arr[i+1] && arr[i] != arr[i + 1] - 1) count += arr[i + 1] - arr[i] - 1; return count; } // Drivers code static public void Main () { int []arr = { 3, 5, 8, 6 }; int n = arr.Length; Console.WriteLine(countNum(arr, n)); } } // This code is contributed by vt_m. |
PHP
<?php // PHP program for // above implementation // Function to count // numbers to be added function countNum( $arr , $n ) { $count = 0; // Sort the array sort( $arr ); // Check if elements are // consecutive or not. // If not, update count for ( $i = 0; $i < $n - 1; $i ++) if ( $arr [ $i ] != $arr [ $i + 1] && $arr [ $i ] != $arr [ $i + 1] - 1) $count += $arr [ $i + 1] - $arr [ $i ] - 1; return $count ; } // Driver code $arr = array (3, 5, 8, 6); $n = count ( $arr ); echo countNum( $arr , $n ) ; // This code is contributed // by anuj_67. ?> |
Javascript
<script> // Javascript program for above implementation // Function to count numbers to be added function countNum(arr, n) { let count = 0; // Sort the array arr.sort(); // Check if elements are consecutive // or not. If not, update count for (let i = 0; i < n - 1; i++) if (arr[i] != arr[i+1] && arr[i] != arr[i + 1] - 1) count += arr[i + 1] - arr[i] - 1; return count; } // Driver code let arr = [ 3, 5, 8, 6 ]; let n = arr.length; document.write(countNum(arr, n)); // This code is contributed by sanjoy_62. </script> |
输出：
2
时间复杂性： O（n日志n） 方法2（使用哈希） 1-维护数组元素的散列。 2-存储最小和最大元素。 3-从散列中的最小元素遍历到最大元素 若元素不在散列中，则进行计数。 4-返回计数。
C++
// C++ program for above implementation #include <bits/stdc++.h> using namespace std; // Function to count numbers to be added int countNum( int arr[], int n) { unordered_set< int > s; int count = 0, maxm = INT_MIN, minm = INT_MAX; // Make a hash of elements // and store minimum and maximum element for ( int i = 0; i < n; i++) { s.insert(arr[i]); if (arr[i] < minm) minm = arr[i]; if (arr[i] > maxm) maxm = arr[i]; } // Traverse all elements from minimum // to maximum and count if it is not // in the hash for ( int i = minm; i <= maxm; i++) if (s.find(arr[i]) == s.end()) count++; return count; } // Drivers code int main() { int arr[] = { 3, 5, 8, 6 }; int n = sizeof (arr) / sizeof (arr[0]); cout << countNum(arr, n) << endl; return 0; } |
JAVA
// Java implementation of the approach import java.util.HashSet; class GFG { // Function to count numbers to be added static int countNum( int arr[], int n) { HashSet<Integer> s = new HashSet<>(); int count = 0 , maxm = Integer.MIN_VALUE, minm = Integer.MAX_VALUE; // Make a hash of elements // and store minimum and maximum element for ( int i = 0 ; i < n; i++) { s.add(arr[i]); if (arr[i] < minm) minm = arr[i]; if (arr[i] > maxm) maxm = arr[i]; } // Traverse all elements from minimum // to maximum and count if it is not // in the hash for ( int i = minm; i <= maxm; i++) if (!s.contains(i)) count++; return count; } // Drivers code public static void main(String[] args) { int arr[] = { 3 , 5 , 8 , 6 }; int n = arr.length; System.out.println(countNum(arr, n)); } } // This code is contributed by Rajput-Ji |
Python3
# Function to count numbers to be added def countNum(arr, n): s = dict () count, maxm, minm = 0 , - 10 * * 9 , 10 * * 9 # Make a hash of elements and store # minimum and maximum element for i in range (n): s[arr[i]] = 1 if (arr[i] < minm): minm = arr[i] if (arr[i] > maxm): maxm = arr[i] # Traverse all elements from minimum # to maximum and count if it is not # in the hash for i in range (minm, maxm + 1 ): if i not in s.keys(): count + = 1 return count # Driver code arr = [ 3 , 5 , 8 , 6 ] n = len (arr) print (countNum(arr, n)) # This code is contributed by mohit kumar |
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function to count numbers to be added static int countNum( int []arr, int n) { HashSet< int > s = new HashSet< int >(); int count = 0, maxm = int .MinValue, minm = int .MaxValue; // Make a hash of elements // and store minimum and maximum element for ( int i = 0; i < n; i++) { s.Add(arr[i]); if (arr[i] < minm) minm = arr[i]; if (arr[i] > maxm) maxm = arr[i]; } // Traverse all elements from minimum // to maximum and count if it is not // in the hash for ( int i = minm; i <= maxm; i++) if (!s.Contains(i)) count++; return count; } // Drivers code public static void Main(String[] args) { int []arr = { 3, 5, 8, 6 }; int n = arr.Length; Console.WriteLine(countNum(arr, n)); } } // This code is contributed by Rajput-Ji |
Javascript
<script> // Javascript implementation of the approach // Function to count numbers to be added function countNum(arr,n) { let s = new Set(); let count = 0, maxm = Number.MIN_VALUE, minm = Number.MAX_VALUE; // Make a hash of elements // and store minimum and maximum element for (let i = 0; i < n; i++) { s.add(arr[i]); if (arr[i] < minm) minm = arr[i]; if (arr[i] > maxm) maxm = arr[i]; } // Traverse all elements from minimum // to maximum and count if it is not // in the hash for (let i = minm; i <= maxm; i++) if (!s.has(i)) count++; return count; } // Drivers code let arr=[3, 5, 8, 6 ]; let n = arr.length; document.write(countNum(arr, n)); // This code is contributed by unknown2108 </script> |
输出：
2
时间复杂性- O（最大值–最小值+1） 本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 写极客。组织 或者把你的文章寄去评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
