关于算法:算法线性时间复杂度的查找算法

43次阅读

共计 555 个字符，预计需要花费 2 分钟才能阅读完成。

给定一无序数组 a[], 求第 k 小的数

public static int randomPartition(int a[], int low, int high) {
  int len = high - low + 1;
  Random rand = new Random();
  int r = rand.nextInt(len) + low;
  int temp = a[r];
  a[r] = a[high];
  a[high] = temp;
  int i = low - 1, j = low;
  int key = a[high];
  for (; j < high; j++) {if (a[j] <= key) {
      i++;
      int temp1 = a[j];
      a[j] = a[i];
      a[i] = temp1;
    }
  }
  i++;
  a[j] = a[i];
  a[i] = key;
  return i;
}

public static int randomSelect(int a[], int low, int high, int i) {if (low == high) {return a[low];
  }
  int q = randomPartition(a, low, high);
  int k = q - low + 1;
  if (i == k)
    return a[q];
  else if (i < k)
    return randomSelect(a, low, q - 1, i);
  else
 return randomSelect(a, q + 1, high, i - k);
}

工夫复杂度 O(n)

正文完