Java 在数组中找到差异为 k 的对数的最佳方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/20171856/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Best way to find the number of pairs in an array whose difference is k
提问by Sahil Gupta
I was solving the problem on hackerrank. I had two approaches in my mind :
我正在解决hackerrank上的问题。我有两种方法：
input : unsorted array(a) and k
输入：未排序的数组（a）和 k
First Approach :
第一种方法：
1) Sort the array
1）对数组进行排序
2) for each array element a[i] ,find the element a[i]+K using binary search.If found increament the count and break the inner loop.
2) 对于每个数组元素 a[i] ，使用二分查找找到元素 a[i]+K。如果找到则增加计数并中断内部循环。
Second Approach :
第二种方法：
1) Sort the array
1）对数组进行排序
2) for each array element a[i] ,find the element a[i]+K using linearsearch.If found increament the count and break the inner loop.
2) 对于每个数组元素 a[i] ，使用线性搜索找到元素 a[i]+K。如果找到则增加计数并中断内部循环。
I found the First approach to be better as it will solve the problem in n(logn). But when multiple test cases are on the solutions the approach 2 takes lesser time . Can some one please explain why ?
我发现第一种方法更好，因为它可以解决 n(logn) 中的问题。但是当解决方案上有多个测试用例时，方法 2 花费的时间更少。有人可以解释为什么吗？
Below are the code for the two approaches :
以下是两种方法的代码：
First Approach Code :
第一种方法代码：
static int pairs(int[] a,int k) {
/* Complete this function */
int temp;
int len=a.length;
int count=0;
int beg;
int mid;
int end;
int midVal;
Arrays.sort(a);
for(int i=0;i<len-1;i++){
temp=a[i]+k;
beg=i+1;
end=len-1;
for(int l=beg;l<len;l++){
mid=(beg+end)/2;
midVal=a[mid];
if(midVal==temp){
count++;
break;
}
else if(midVal>temp){
end=mid-1;
}
else{
beg=mid+1;
}
}
}
return count;
}
Second Approach Code :
第二种方法代码：
static int pairs(int[] a,int k) {
/* Complete this function */
int temp;
int len=a.length;
int count=0;
Arrays.sort(a);
for(int i=0;i<len;i++){
temp=a[i];
for(int j=i+1;j<len;j++){
if(temp-a[j]==-k){
count++;
break;
}
}
}
return count;
}
回答by Abhishek Bansal
In your 1st code, your inner loop termination condition is incorrect. It should terminate if the begand endpointers cross each other.
在您的第一个代码中，您的内循环终止条件不正确。如果beg和end指针相互交叉，它应该终止。
Change it to while (beg <= end)or for (; beg <= end; )
将其更改为while (beg <= end)或for (; beg <= end; )
Also, for the second approach there is no need for sorting the array.
此外，对于第二种方法，不需要对数组进行排序。
回答by Vikram Bhat
The first approach is the best here among the two but there is better approach than both:-
第一种方法是两者中最好的方法，但有比两者更好的方法：-
Here a pseudo code for a better approach:-
这是一个更好的方法的伪代码：-
for(i=0;i<Arr.length;i++) {
Hashmap.add(Arr[i])
}
count=0;
for(j=0;j<Arr.length;j++) {
if(Hashmap.containsKey(Arr[j]+k))
count++;
}
Time complexity: O(N) whereas your approach = O(NlogN)
时间复杂度：O(N) 而你的方法 = O(NlogN)
Edit:-
编辑：-
Note:-My approach has extra space complexity of O(N) for Hash table whereas suggested approach is inplace.
注意：-我的方法对于哈希表具有 O(N) 的额外空间复杂度，而建议的方法是适当的。
回答by fatih tekin
You can also use set no need to use hashmap
您也可以使用 set 无需使用 hashmap
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int[] firstLine = Stream.of(in.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
int count = firstLine[0];
int diff = firstLine[1];
Set<Integer> numbers = new HashSet<Integer>(Stream.of(in.readLine().split(" ")).map(Integer::valueOf).collect(Collectors.toList()));
int pairCount = 0;
for (Integer number : numbers) {
pairCount += (numbers.contains(number+diff) ? 1:0);
}
System.out.println(pairCount);
}
回答by Saif ali Karedia
private static int CountDistinctPairs(int[] nums, int k) {
// TODO Auto-generated method stub
HashMap<Integer, Boolean> map = new HashMap<Integer, Boolean>();
HashSet<String> set = new HashSet<String>();
for(int i =0;i < nums.length;i++){
map.put(nums[i],true);
}
for (int i = 0 ; i < nums.length; i++){
if(map.containsKey(nums[i]+k)){
String a = "";
if(nums[i]<nums[i]+k){
a = "("+nums[i]+","+(nums[i]+k)+")";
}
else{
a = "("+(nums[i] + k)+","+nums[i]+")";
}
set.add(a);
}
}
System.out.println(set);
return set.size();
}
回答by Deepak Maddeshiya
static boolean checkDuplicatesWithinK(int arr[], int k)
{
// Creates an empty hashset
HashSet<Integer> set = new HashSet<>();
// Traverse the input array
for (int i=0; i<arr.length; i++)
{
// If already present n hash, then we found
// a duplicate within k distance
if (set.contains(arr[i]))
return true;
// Add this item to hashset
set.add(arr[i]);
// Remove the k+1 distant item
if (i >= k)
set.remove(arr[i-k]);
}
return false;
}
public static void main (String[] args)
{
int arr[] = {10, 5, 3, 4, 3, 5, 6};
if (checkDuplicatesWithinK(arr, 3))
System.out.println("Yes");
else
System.out.println("No");
}
回答by Wei-Hsuan Chou
My solution
我的解决方案
System.out.println("findPair:"+findPair(new int[]{4,7,1,2,5,3,0,7,8,5,2}, 3));
System.out.println("findPair:"+findPair(new int[]{4,7,1,2,5,3,0,7,8,5,2}, 3));
public static int findPair(int[] nums, int target){
Arrays.sort(nums);
int count = 0;
String pairText = "";
for(int i =0; i < nums.length;i++){
for(int j =i+1; j < nums.length;j++){
if(nums[j]-nums[i] == target && (!pairText.equals(nums[i]+", "+nums[j]))){
//System.out.println(nums[i]+", "+nums[j]);
pairText = nums[i]+", "+nums[j];
count++;
}
}
}
return count;
}
