给定一个未排序的数组和一个数字n，找出数组中是否存在一对差为n的元素。 例如：
null
Input: arr[] = {5, 20, 3, 2, 50, 80}, n = 78Output: Pair Found: (2, 80)Input: arr[] = {90, 70, 20, 80, 50}, n = 45Output: No Such Pair
最简单的方法是运行两个循环，外循环选择第一个元素（较小的元素），内循环寻找外循环选择的元素加上n。该方法的时间复杂度为O（n^2）。 我们可以使用排序和二进制搜索将时间复杂度提高到O（nLogn）。第一步是按升序对数组排序。数组排序后，从左到右遍历数组，对于每个元素arr[i]，在arr[i+1..n-1]中对arr[i]+n进行二进制搜索。如果找到元素，则返回该对。 第一步和第二步都采用O（nLogn）。所以总体复杂度是O（nLogn）。 上述算法的第二步可以改进为O（n）。第一步保持不变。第二步的想法是取两个索引变量i和j，分别将它们初始化为0和1。现在运行一个线性循环。如果arr[j]–arr[i]小于n，我们需要寻找更大的arr[j]，所以增量j。如果arr[j]–arr[i]大于n，我们需要寻找更大的arr[i]，所以增量i。感谢Aashish Barnwal提出这种方法。 以下代码仅用于算法的第二步，它假设数组已经排序。
C++
// C++ program to find a pair with the given difference #include <bits/stdc++.h> using namespace std; // The function assumes that the array is sorted bool findPair( int arr[], int size, int n) { // Initialize positions of two elements int i = 0; int j = 1; // Search for a pair while (i < size && j < size) { if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n) ) { cout << "Pair Found: (" << arr[i] << ", " << arr[j] << ")" ; return true ; } else if (arr[j]-arr[i] < n) j++; else i++; } cout << "No such pair" ; return false ; } // Driver program to test above function int main() { int arr[] = {1, 8, 30, 40, 100}; int size = sizeof (arr)/ sizeof (arr[0]); int n = -60; findPair(arr, size, n); return 0; } // This is code is contributed by rathbhupendra |
C
// C program to find a pair with the given difference #include <stdio.h> // The function assumes that the array is sorted bool findPair( int arr[], int size, int n) { // Initialize positions of two elements int i = 0; int j = 1; // Search for a pair while (i<size && j<size) { if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n)) { printf ( "Pair Found: (%d, %d)" , arr[i], arr[j]); return true ; } else if (arr[j]-arr[i] < n) j++; else i++; } printf ( "No such pair" ); return false ; } // Driver program to test above function int main() { int arr[] = {1, 8, 30, 40, 100}; int size = sizeof (arr)/ sizeof (arr[0]); int n = -60; findPair(arr, size, n); return 0; } |
JAVA
// Java program to find a pair with the given difference import java.io.*; class PairDifference { // The function assumes that the array is sorted static boolean findPair( int arr[], int n) { int size = arr.length; // Initialize positions of two elements int i = 0 , j = 1 ; // Search for a pair while (i < size && j < size) { if (i != j && (arr[j] - arr[i] == n || arr[i] - arr[j] == n)) { System.out.print( "Pair Found: " + "( " +arr[i]+ ", " + arr[j]+ " )" ); return true ; } else if (arr[j] - arr[i] < n) j++; else i++; } System.out.print( "No such pair" ); return false ; } // Driver program to test above function public static void main (String[] args) { int arr[] = { 1 , 8 , 30 , 40 , 100 }; int n = - 60 ; findPair(arr,n); } } /*This code is contributed by Devesh Agrawal*/ |
python
# Python program to find a pair with the given difference # The function assumes that the array is sorted def findPair(arr,n): size = len (arr) # Initialize positions of two elements i,j = 0 , 1 # Search for a pair while i < size and j < size: if i ! = j and arr[j] - arr[i] = = n: print "Pair found (" ,arr[i], "," ,arr[j], ")" return True elif arr[j] - arr[i] < n: j + = 1 else : i + = 1 print "No pair found" return False # Driver function to test above function arr = [ 1 , 8 , 30 , 40 , 100 ] n = 60 findPair(arr, n) # This code is contributed by Devesh Agrawal |
C#
// C# program to find a pair with the given difference using System; class GFG { // The function assumes that the array is sorted static bool findPair( int []arr, int n) { int size = arr.Length; // Initialize positions of two elements int i = 0, j = 1; // Search for a pair while (i < size && j < size) { if (i != j && arr[j] - arr[i] == n) { Console.Write( "Pair Found: " + "( " + arr[i] + ", " + arr[j] + " )" ); return true ; } else if (arr[j] - arr[i] < n) j++; else i++; } Console.Write( "No such pair" ); return false ; } // Driver program to test above function public static void Main () { int []arr = {1, 8, 30, 40, 100}; int n = 60; findPair(arr, n); } } // This code is contributed by Sam007. |
PHP
<?php // PHP program to find a pair with // the given difference // The function assumes that the // array is sorted function findPair(& $arr , $size , $n ) { // Initialize positions of // two elements $i = 0; $j = 1; // Search for a pair while ( $i < $size && $j < $size ) { if ( $i != $j && $arr [ $j ] - $arr [ $i ] == $n ) { echo "Pair Found: " . "(" . $arr [ $i ] . ", " . $arr [ $j ] . ")" ; return true; } else if ( $arr [ $j ] - $arr [ $i ] < $n ) $j ++; else $i ++; } echo "No such pair" ; return false; } // Driver Code $arr = array (1, 8, 30, 40, 100); $size = sizeof( $arr ); $n = 60; findPair( $arr , $size , $n ); // This code is contributed // by ChitraNayal ?> |
Javascript
<script> // JavaScript program for the above approach // The function assumes that the array is sorted function findPair(arr, size, n) { // Initialize positions of two elements let i = 0; let j = 1; // Search for a pair while (i < size && j < size) { if (i != j && arr[j] - arr[i] == n) { document.write( "Pair Found: (" + arr[i] + ", " + arr[j] + ")" ); return true ; } else if (arr[j] - arr[i] < n) j++; else i++; } document.write( "No such pair" ); return false ; } // Driver program to test above function let arr = [1, 8, 30, 40, 100]; let size = arr.length; let n = 60; findPair(arr, size, n); // This code is contributed by Potta Lokesh </script> |
输出
Pair Found: (100, 40)
哈希也可以用来解决这个问题。创建一个空的哈希表。遍历数组，使用数组元素作为散列键，并在HT中输入它们。再次遍历数组，在HT中查找值n+arr[i]。
C++
// C++ program to find a pair with the given difference #include <bits/stdc++.h> using namespace std; // The function assumes that the array is sorted bool findPair( int arr[], int size, int n) { unordered_map< int , int > mpp; for ( int i = 0; i < size; i++) { mpp[arr[i]]++; } for ( int i = 0; i < size; i++) { if (mpp.find(n + arr[i]) != mpp.end()) { cout << "Pair Found: (" << arr[i] << ", " << n + arr[i] << ")" ; return true ; } } cout << "No Pair found" ; return false ; } // Driver program to test above function int main() { int arr[] = { 1, 8, 30, 40, 100 }; int size = sizeof (arr) / sizeof (arr[0]); int n = -60; findPair(arr, size, n); return 0; } |
输出
Pair Found: (100, 40)
如果您发现上述任何代码/算法不正确，请写下评论，或者寻找其他方法来解决相同的问题。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
