给定一个已排序的整数数组，返回数组元素中不同绝对值的数目。输入可以包含重复的值。 例如：
null
Input: [-3, -2, 0, 3, 4, 5]Output: 5There are 5 distinct absolute valuesamong the elements of this array, i.e.0, 2, 3, 4 and 5)Input: [-1, -1, -1, -1, 0, 1, 1, 1, 1]Output: 2Input: [-1, -1, -1, -1, 0]Output: 2Input: [0, 0, 0]Output: 1
解决方案应该只对输入数组进行一次扫描，并且不应该使用任何额外的空间。i、 e.预期时间复杂度为O（n），辅助空间为O（1）。
一个简单的解决方案是使用set。对于输入数组的每个元素，我们在集合中插入其绝对值。由于set不支持重复的元素，元素的绝对值将只插入一次。因此，所需的计数是集合的大小。 下面是这个想法的实施。
C++
// C++ program to find absolute distinct // count of an array in O(n) time. #include <bits/stdc++.h> using namespace std; // The function returns number of // distinct absolute values among // the elements of the array int distinctCount( int arr[], int n) { unordered_set< int > s; // Note that set keeps only one // copy even if we try to insert // multiple values for ( int i = 0 ; i < n; i++) s.insert( abs (arr[i])); return s.size(); } // Driver code int main() { int arr[] = {-2, -1, 0, 1, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Count of absolute distinct values : " << distinctCount(arr, n); return 0; } |
JAVA
// java code to find absolute distinct // count of an array in O(n) time. import java.util.*; class GFG { // The function returns number of // distinct absolute values among // the elements of the array static int distinctCount( int arr[], int n) { Set<Integer> s = new HashSet<Integer> (); // Note that set keeps only one // copy even if we try to insert // multiple values for ( int i = 0 ; i < n; i++) s.add(Math.abs(arr[i])); return s.size(); } // Driver code public static void main(String[] args) { int arr[] = {- 2 , - 1 , 0 , 1 , 1 }; int n = arr.length; System.out.println( "Count of absolute distinct values : " + distinctCount(arr, n)); } } // This code is contributed by prerna saini |
Python3
# Python3 code to find absolute distinct # count of an array in O(n) time. # This function returns number of # distinct absolute values among # the elements of the array def distinctCount(arr, n): s = set () # set keeps all unique elements for i in range (n): s.add( abs (arr[i])) return len (s) # Driver Code arr = [ - 2 , - 1 , 0 , 1 , 1 ] n = len (arr) print ( "Count of absolute distinct values:" , distinctCount(arr, n)) # This code is contributed # by Adarsh_Verma |
C#
// C# code to find absolute distinct // count of an array in O(n) time. using System; using System.Collections.Generic; class GFG { // The function returns number of // distinct absolute values among // the elements of the array static int distinctCount( int []arr, int n) { HashSet< int > s = new HashSet< int >(); // Note that set keeps only one // copy even if we try to insert // multiple values for ( int i = 0 ; i < n; i++) s.Add(Math.Abs(arr[i])); return s.Count; } // Driver code public static void Main() { int []arr = {-2, -1, 0, 1, 1}; int n = arr.Length; Console.Write( "Count of absolute distinct values : " + distinctCount(arr, n)); } } // This code is contributed by PrinciRaj1992 |
Javascript
<script> // Javascript code to find absolute distinct // count of an array in O(n) time. // The function returns number of // distinct absolute values among // the elements of the array function distinctCount(arr, n) { let s = new Set(); // Note that set keeps only one // copy even if we try to insert // multiple values for (let i = 0 ; i < n; i++) s.add(Math.abs(arr[i])); return s.size; } let arr = [-2, -1, 0, 1, 1]; let n = arr.length; document.write( "Count of absolute distinct values : " + distinctCount(arr, n)); </script> |
输出：
Count of absolute distinct values : 3
时间复杂性： O（n） 辅助空间： O（n） 上述实现需要O（n）额外空间，如何在O（1）额外空间中实现？ 这样做的目的是利用数组已经排序的事实。我们将不同元素的计数初始化为数组中的元素数。我们从数组两个角的两个索引变量开始，检查输入数组中的pair，sum为0。如果找到和为0的对或遇到重复项，我们将减少不同元素的计数。最后我们返回更新的计数。 下面是上述方法的实现。
C++
// C++ program to find absolute distinct // count of an array using O(1) space. #include <bits/stdc++.h> using namespace std; // The function returns return number // of distinct absolute values // among the elements of the array int distinctCount( int arr[], int n) { // initialize count as number of elements int count = n; int i = 0, j = n - 1, sum = 0; while (i < j) { // Remove duplicate elements from the // left of the current window (i, j) // and also decrease the count while (i != j && arr[i] == arr[i + 1]) count--, i++; // Remove duplicate elements from the // right of the current window (i, j) // and also decrease the count while (i != j && arr[j] == arr[j - 1]) count--, j--; // break if only one element is left if (i == j) break ; // Now look for the zero sum pair // in current window (i, j) sum = arr[i] + arr[j]; if (sum == 0) { // decrease the count if (positive, // negative) pair is encountered count--; i++, j--; } else if (sum < 0) i++; else j--; } return count; } // Driver code int main() { int arr[] = {-2, -1, 0, 1, 1}; int n = sizeof (arr)/ sizeof (arr[0]); cout << "Count of absolute distinct values : " << distinctCount(arr, n); return 0; } |
JAVA
// Java program to find absolute distinct // count of an array using O(1) space. import java.io.*; class GFG { // The function returns return number // of distinct absolute values // among the elements of the array static int distinctCount( int arr[], int n) { // initialize count as number of elements int count = n; int i = 0 , j = n - 1 , sum = 0 ; while (i < j) { // Remove duplicate elements from the // left of the current window (i, j) // and also decrease the count while (i != j && arr[i] == arr[i + 1 ]) { count--; i++; } // Remove duplicate elements from the // right of the current window (i, j) // and also decrease the count while (i != j && arr[j] == arr[j - 1 ]) { count--; j--; } // break if only one element is left if (i == j) break ; // Now look for the zero sum pair // in current window (i, j) sum = arr[i] + arr[j]; if (sum == 0 ) { // decrease the count if (positive, // negative) pair is encountered count--; i++; j--; } else if (sum < 0 ) i++; else j--; } return count; } // Driver code public static void main (String[] args) { int arr[] = {- 2 , - 1 , 0 , 1 , 1 }; int n = arr.length; System.out.println ( "Count of absolute distinct values : " + distinctCount(arr, n)); } } |
Python3
# Python3 program to find absolute distinct # count of an array using O(1) space. # The function returns return number # of distinct absolute values # among the elements of the array def distinctCount(arr, n): # initialize count as number of elements count = n; i = 0 ; j = n - 1 ; sum = 0 ; while (i < j): # Remove duplicate elements from the # left of the current window (i, j) # and also decrease the count while (i ! = j and arr[i] = = arr[i + 1 ]): count = count - 1 ; i = i + 1 ; # Remove duplicate elements from the # right of the current window (i, j) # and also decrease the count while (i ! = j and arr[j] = = arr[j - 1 ]): count = count - 1 ; j = j - 1 ; # break if only one element is left if (i = = j): break ; # Now look for the zero sum pair # in current window (i, j) sum = arr[i] + arr[j]; if ( sum = = 0 ): # decrease the count if (positive, # negative) pair is encountered count = count - 1 ; i = i + 1 ; j = j - 1 ; else if ( sum < 0 ): i = i + 1 ; else : j = j - 1 ; return count; # Driver code arr = [ - 2 , - 1 , 0 , 1 , 1 ]; n = len (arr); print ( "Count of absolute distinct values : " , distinctCount(arr, n)); # This code is contributed # by Akanksha Rai |
C#
//C# program to find absolute distinct // count of an array using O(1) space. using System; class GFG { // The function returns return number // of distinct absolute values // among the elements of the array static int distinctCount( int []arr, int n) { // initialize count as number of elements int count = n; int i = 0, j = n - 1, sum = 0; while (i < j) { // Remove duplicate elements from the // left of the current window (i, j) // and also decrease the count while (i != j && arr[i] == arr[i + 1]) { count--; i++; } // Remove duplicate elements from the // right of the current window (i, j) // and also decrease the count while (i != j && arr[j] == arr[j - 1]) { count--; j--; } // break if only one element is left if (i == j) break ; // Now look for the zero sum pair // in current window (i, j) sum = arr[i] + arr[j]; if (sum == 0) { // decrease the count if (positive, // negative) pair is encountered count--; i++; j--; } else if (sum < 0) i++; else j--; } return count; } // Driver code public static void Main () { int []arr = {-2, -1, 0, 1, 1}; int n = arr.Length; Console.WriteLine( "Count of absolute distinct values : " + distinctCount(arr, n)); // This code is contributed by inder_verma } } |
PHP
<?php // PHP program to find absolute distinct // count of an array using O(1) space. // The function returns return number // of distinct absolute values // among the elements of the array function distinctCount( $arr , $n ) { // initialize count as number // of elements $count = $n ; $i = 0; $j = $n - 1; $sum = 0; while ( $i < $j ) { // Remove duplicate elements from the // left of the current window (i, j) // and also decrease the count while ( $i != $j && $arr [ $i ] == $arr [ $i + 1]) { $count --; $i ++;} // Remove duplicate elements from the // right of the current window (i, j) // and also decrease the count while ( $i != $j && $arr [ $j ] == $arr [ $j - 1]) { $count --; $j --;} // break if only one element is left if ( $i == $j ) break ; // Now look for the zero sum pair // in current window (i, j) $sum = $arr [ $i ] + $arr [ $j ]; if ( $sum == 0) { // decrease the count if (positive, // negative) pair is encountered $count --; $i ++; $j --; } else if ( $sum < 0) $i ++; else $j --; } return $count ; } // Driver code $arr = array (-2, -1, 0, 1, 1); $n = sizeof( $arr ); echo "Count of absolute distinct values : " . distinctCount( $arr , $n ); // This code is contributed // by Akanksha Rai ?> |
Javascript
<script> // Javascript program to find absolute distinct // count of an array using O(1) space. // The function returns return number // of distinct absolute values // among the elements of the array function distinctCount(arr, n) { // initialize count as number of elements let count = n; let i = 0, j = n - 1, sum = 0; while (i < j) { // Remove duplicate elements from the // left of the current window (i, j) // and also decrease the count while (i != j && arr[i] == arr[i + 1]) count--, i++; // Remove duplicate elements from the // right of the current window (i, j) // and also decrease the count while (i != j && arr[j] == arr[j - 1]) count--, j--; // break if only one element is left if (i == j) break ; // Now look for the zero sum pair // in current window (i, j) sum = arr[i] + arr[j]; if (sum == 0) { // decrease the count if (positive, // negative) pair is encountered count--; i++, j--; } else if (sum < 0) i++; else j--; } return count; } let arr = [-2, -1, 0, 1, 1]; let n = arr.length; document.write( "Count of absolute distinct values : " + distinctCount(arr, n)); </script> |
输出：
Count of absolute distinct values : 3
时间复杂性： O（n） 辅助空间： O（1） 本文由 阿迪蒂亚·戈尔 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以写一篇文章，然后将文章邮寄给评论-team@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
