找到差值为k的数组中对的数量的最佳方法

Question

我正在解决hackerrank的问题.我脑子里有两种方法:

输入:未排序的数组(a)和k

第一种方法:

1)对数组进行排序

2)对于每个数组元素a [i],使用二分搜索找到元素a [i] + K.If发现递增计数并打破内循环.

第二种方法:

1)对数组进行排序

2)对于每个数组元素a [i],使用linearsearch找到元素a [i] + K.If发现递增计数并打破内部循环.

我发现第一种方法更好,因为它将解决n(logn)中的问题.但是当解决方案中存在多个测试用例时,方法2需要较少的时间.有人可以解释一下原因吗？

以下是两种方法的代码:

第一种方法代码:

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;
}

第二种方法代码:

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;
}

Answer 1

第一种方法是两者中最好的方法,但有比两者更好的方法: -

这里有一个伪代码,用于更好的方法: -

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++;

}

时间复杂度:O(N)而你的方法= O(NlogN)

编辑:-

注意: -我的方法对Hash表有额外的空间复杂度O(N),而建议的方法就位.