如何找到最大值 和分钟.在数组中使用最小比较？

Question

这是一个面试问题:给定一组整数找到最大值.和分钟.使用最小比较.

显然,我可以循环数组两次并~2n在最坏的情况下使用比较,但我想做得更好.

Answer 1

1. Pick 2 elements(a, b), compare them. (say a > b)
2. Update min by comparing (min, b)
3. Update max by comparing (max, a)

这样,您将对2个元素进行3次比较,相当于元素的3N/2总比较N.

Answer 2

试图通过srbh.kmr改进答案.假设我们有序列:

A = [a1, a2, a3, a4, a5]

比较a1与a2和计算min12,max12:

if (a1 > a2)
  min12 = a2
  max12 = a1
else
  min12 = a1
  max12 = a2

同样计算min34,max34.既然a5是独自一人,那就保持原样......

现在比较min12与min34和计算min14,同样计算max14.最后比较min14和a5计算min15.同样计算max15.

总共它只有6个比较!

该解决方案可以扩展为任意长度的数组.可能可以通过类似的合并排序方法来实现(将数组分成两半并计算min max每一半).

更新:这是C中的递归代码:

#include <stdio.h>

void minmax (int* a, int i, int j, int* min, int* max) {
  int lmin, lmax, rmin, rmax, mid;
  if (i == j) {
    *min = a[i];
    *max = a[j];
  } else if (j == i + 1) {
    if (a[i] > a[j]) {
      *min = a[j];
      *max = a[i];
    } else {
      *min = a[i];
      *max = a[j];
    }
  } else {
    mid = (i + j) / 2;
    minmax(a, i, mid, &lmin, &lmax);
    minmax(a, mid + 1, j, &rmin, &rmax);
    *min = (lmin > rmin) ? rmin : lmin;
    *max = (lmax > rmax) ? lmax : rmax;
  }
}

void main () {
  int a [] = {3, 4, 2, 6, 8, 1, 9, 12, 15, 11};
  int min, max;
  minmax (a, 0, 9, &min, &max);
  printf ("Min : %d, Max: %d\n", min, max);
}

现在我无法根据N(数组中元素的数量)计算确切的比较数.但是很难看出人们如何能够在这么多的比较之下.

更新:我们可以计算出如下比较的数量:

在这个计算树的底部,我们从原始数组中形成整数对.所以我们有N / 2叶子节点.对于这些叶节点中的每一个,我们进行了1次比较.

通过引用完美二叉树的属性,我们得到:

leaf nodes (L) = N / 2 // known
total nodes (n) = 2L - 1 = N - 1
internal nodes = n - L = N / 2 - 1

对于每个内部节点,我们进行2次比较.因此,我们进行了N - 2比较.与N / 2叶节点的比较一起,我们进行了(3N / 2) - 2总体比较.

所以,这可能是他的回答中隐含的解决方案srbh.kmr.

Answer 3

去分而治之!

1,3,2,5

对于这个发现min,max将进行6次比较

除了他们

1,3 --->将在一次比较中给出min 1和max 3. 2,5 --->将在一次比较中给出min 2和max 5

现在我们可以比较两个分钟(1,2) - >将最终分钟作为1(一个比较)同样两个最大(3,5)--->将给出最终最大值为5(一个比较)

所以完全是四个比较

Answer 4

一种稍微不同的方法，它使用整数算术而不是比较（没有明确禁止）

for(int i=0;i<N;i++) {
  xmin += x[i]-xmin & x[i]-xmin>>31;
  xmax += x[i]-xmax & xmax-x[i]>>31;
}