从两个排序的数组中找到第k个最小元素

3 回答

• 0

  在StackOverflow上已经有很好的解决方案，例如here和here，所以我将专注于识别错误：

  这一行：

  if ((midA-p1+midB-p2+2) < k) {
  

  应修改为使用 <= ：

  if ((midA-p1+midB-p2+2) <= k) {
  

  您可以通过以下小例子了解为什么需要这样做：

  A = {1,3}
  B = {2}
  

  其他变量将是：

  p1 = p2 = r2 = midA = midB = 0
  r1 = 1
  

  所以表达式 midA-p1+midB-p2+2 将是 2 . 在这种情况下，你显然想要丢弃A的元素，而不是B的唯一元素 .

  请注意，通常可以包含执行 if 块的k情况，因为您永远不会丢弃k（即太多）元素：作为递归调用的最后一个参数传递的表达式总是最多K-1 .

  另一方面，当 if 表达式为k时，转到 else 部分是错误的，因为midA或midB可能是该第k个元素的索引，并且它将被抛出 .

  回复于 2024-05-03T01:52:24+08:00
• 2

  如果我能在你的代码片段中找到错误，我会更新我的答案 . 现在你可以看看我的代码哪个逻辑与你的完全相同，除了：

  该策略基本上是根据长度条件比较两个子阵列的中间索引元素 .

  简单和我的代码的小尺寸的主要区别是我避免了一些if-else条件（对于长度条件）通过在第一个数组/索引对不小的情况下调用交换其参数的函数 .

  public static int findKth(int[] A, int i, int[] B, int j, int k) {
  
      // Here is the simple trick. We've just changed the parameter order if first array is not smaller.
      // so that later we won't need to write if-else conditions to check smaller/greater stuff
      if((A.length - i) > (B.length - j))
      {
          return findKth(B, j, A, i, k);
      }
  
      if(i >= A.length) 
      {
          return B[j + k - 1];
      }
      if(k == 1)
      {
          return Math.min(A[i], B[j]);
      }
  
      int aMid = Math.min(k / 2, A.length - i);
      int bMid = k - aMid;
  
      if(A[i + aMid - 1] <= B[j + bMid - 1])
      {
          return findKth(A, i + aMid, B, j, k - aMid);
      }
  
      return findKth(A, i, B, j + bMid, k - bMid);
  }
  
  public static int findKthSmallestElement(int[] A, int[] B, int k)
  {
      if(k > A.length + B.length)
          return -1;
  
      return findKth(A, 0, B, 0, k);
  }
  

  时间复杂度是 O(log(m + n)) .

  回复于 2024-05-03T01:52:24+08:00
• 0

  #include <bits/stdc++.h>
  using namespace std;
  
  int findKthElement(int a[],int start1,int end1,int b[],int start2,int end2,int k){
      if(start1 >= end1)return b[start2+k-1];
      if(start2 >= end2)return a[start1+k-1];
      if(k==1)return min(a[start1],b[start2]);
      int aMax = INT_MAX;
      int bMax = INT_MAX;
      if(start1+k/2-1 < end1) aMax = a[start1 + k/2 - 1];
      if(start2+k/2-1 < end2) bMax = b[start2 + k/2 - 1];
  
      if(aMax > bMax){
          return findKthElement(a,start1,end1,b,start2+k/2,end2,k-k/2);
      }
      else{
          return findKthElement(a,start1 + k/2,end1,b,start2,end2,k-k/2);
      }
  }
  
  int main(void){
      int t;
      scanf("%d",&t);
      while(t--){
          int n,m,k;
          cout<<"Enter the size of 1st Array"<<endl;
          cin>>n;
          int arr[n];
          cout<<"Enter the Element of 1st Array"<<endl;
          for(int i = 0;i<n;i++){
              cin>>arr[i];
          }
          cout<<"Enter the size of 2nd Array"<<endl;
          cin>>m;
          int arr1[m];
          cout<<"Enter the Element of 2nd Array"<<endl;
          for(int i = 0;i<m;i++){
              cin>>arr1[i];
          }
          cout<<"Enter The Value of K";
          cin>>k;
          sort(arr,arr+n);
          sort(arr1,arr1+m);
          cout<<findKthElement(arr,0,n,arr1,0,m,k)<<endl;
      }
  
      return 0;
  }
  

  时间复杂度为O（log（min（m，n）））

  回复于 2024-05-03T01:52:24+08:00