查找数组中值的组合，其中每个值都大于另一个值

问题描述 投票：3回答：3

我在代码访谈中收到一个问题，遗憾的是我无法以有效的方式解决。我把它解决为O（n ^ 2）并且我相信它可以在O（n log n）中解决。

这是我的尝试，它是解决它的正确方法还是可以改进？

Question

你有所有包含A整数值的数组B，C和n。如果B中的值必须高于A，并且C必须高于B，则我们可以在A，B和C之间找到多少个值组合。

EG

A = [29, 49, 65]
B = [31, 55, 78]
C = [45, 98, 100]

# Combinations
29, 31, 45
29, 31, 98
29, 31, 100
29, 55, 98
29, 55, 100
49, 55, 98
49, 55, 100
65, 78, 98
65, 78, 100

Solution

我通过对列表进行排序然后对最接近的索引进行二进制搜索来解决它，并且高于之前的值。

def getClosest(arr, left, right, val, closest=None):
  mid = right-int(abs(left-right)/2)
  if left >= right:
    if arr[mid] == val:
      return val
    return closest

  if arr[mid] == val:
    return mid
  elif val > arr[mid]:
    return getClosest(arr, mid+1, right, val, closest)
  elif val < arr[mid]:
    if closest is None or mid < closest:
      closest = mid
    return getClosest(arr, left, mid-1, val, closest)

  return closest

def getLocationGTE(arr, limit):
  index = getClosest(arr, 0, len(arr)-1, limit)
  if index is None:
    return []
  else:
    return arr[index:]

def countStops(A, B, C):
  A.sort()
  B.sort()
  C.sort()
  total = 0
  for i in range(len(A)):
    a = A[i]
    b_locations = getLocationGTE(B, a+1)
    for b in b_locations:
      c_locations = getLocationGTE(C, b+1)
      total += len(c_locations)

  return total
algorithm big-o
3个回答
2
投票

到目前为止给出的答案看起来有点复杂，所以让我添加另一种方法。

主要思想是使用给定的B元素计算组合的数量。它是较小的A元素的数量乘以较大的C元素的数量。

我们假设所有三个数组都按升序排序。您的示例数组已经排序，但事实并未在文本中明确提及，因此我们可能需要初始排序，计算O（nlogn）。

我们需要在所有B元素上循环，并且在循环内部我们需要将两个索引维护到A和C数组中，A索引ia标识最后一个A元素低于B元素，C索引ic标识第一个C元素大于B元素。该循环为O（n），因为A和C索引不能增加n次以上。

实现该算法的Java类：

public class Combinations {

    // array access guarded against index-out-of-range.
    private static int arrayAccess(int[] array, int index) {
        if (index < 0)                  return Integer.MIN_VALUE;
        else if (index >= array.length) return Integer.MAX_VALUE;
        else                            return array[index];
    }

    public static int combinations(int[] a, int[] b, int[] c) {
        int ia = -1;
        int ic = 0;
        int nCombinations = 0;
        for (int ib=0; ib<b.length; ib++) {
            int bElement = b[ib];
            while (arrayAccess(a, ia+1) < bElement) {
                ia++;
            }
            while (arrayAccess(c, ic) <= bElement) {
                ic++;
            }
            nCombinations += (ia+1) * (c.length-ic);
        }
        return nCombinations;
    }

    public static void main(String[] args) {
        int[] a = {29, 49, 65};
        int[] b = {31, 55, 78};
        int[] c = {45, 98, 100};
        int result = combinations(a, b, c);
        System.out.println(result);
    }
}
0
投票

是的，你是对的，它可以在O（nlogn）中解决。

  1. 排序所有数组
  2. 对于B中的每个索引b，计算C中有多少元素大于B [b]
    int[] count = new int[n];
    int c = 0;
    for (int b = 0; b < n; b++) {
        while (c < n && C[c] <= B[b])
            c++;
        count[b] = n - c;
    }
  1. 反向建立累计计数总和
    int[] cumSum = new int[n];
    cumSum[n - 1] = count[n - 1];
    for (int i = n - 2; i >= 0; i--)
        cumSum[i] = cumSum[i + 1] + count[i];
  1. 对于A中的每个元素，找到B中的第一个索引，并将相应的累积总和添加到总计数中
    int total = 0, b = 0;
    for (int a = 0; a < n; a++) {
        while (b < n && B[b] <= A[a])
            b++;
        if (b == n)
            break;
        total += cumSum[b];
    }

步骤1.取O（nlogn），步骤2.到4.是O（n），总体给出O（nlogn）。

这是javascript中的完整实现：

function countCombos(A, B, C) {
  A.sort(function (a, b) {return a - b})
  B.sort(function (a, b) {return a - b})
  C.sort(function (a, b) {return a - b})
  let count = [], c = 0, n = A.length
  for (let b = 0; b < n; b++) {
    while (c < n && C[c] <= B[b])
      c++
    count[b] = n - c
  }
  for (let i = n - 2; i >= 0; i--) // building cumSum directly in count
    count[i] = count[i] + count[i + 1]
  let total = 0, b = 0
  for (let a = 0; a < n; a++) {
    while (b < n && B[b] <= A[a])
      b++
    if (b == n)
      break
    total += count[b]
  }
  return total
}

console.log(countCombos([29, 49, 65], [31, 55, 78], [45, 98, 100]))

顺便说一句。你在列表中缺少4个组合：[29,78,98]，[29,78,100]，[49,78,98]和[49,78,100]，因此13是正确的答案。

0
投票

你的直觉是正确的，我们可以击败O(n^2)，因为排序和二进制搜索解决方案会产生额外的工作（数组元素B和C被多次读取），我们希望避免。

Solution A - O(n.log2(n))

可以使用二叉搜索树作为辅助数据结构来构造O(nlogn)解。我们需要用颜色装饰每个节点，标识从中提取节点值的数组。

让我们使用例如以下颜色约定：

  • Amber为阵列A
  • Blue为阵列B
  • Cyan为阵列C

然后，我们执行树的有序深度优先搜索，计算Cyan节点，Cyan -> ... -> Blue和Cyan -> ... -> Blue -> ... -> Amber过渡的数量。

BST tree = new BST(AscendingOrder);

for (a: A) { tree.add(new Node(Amber, a)); }
for (b: B) { tree.add(new Node(Blue, b));  }
for (c: C) { tree.add(new Node(Cyan, c));  }

int cyans, cyanThenBlues, solutions = 0;
DFS(tree.root(), cyans, cyanThenBlues, solutions)

同

DFS(Node node, int& cyans, int& cyanThenBlues, int& solutions) {
   if (node == null) { return; }

   DFS(node.left(), cyans, cyanThenBlues, solutions);            

   cyans += node.color() == Cyan ? 1 : 0;
   cyanThenBlues += node.color() == Blue ? cyans : 0;
   solutions += node.color() == Amber ? cyanThenBlues : 0;

   DFS(node.right(), cyans, cyanThenBlues, solutions);
}

如果A，B和C的值是任意排序的，那么BST的构造将花费O(n.log2(n))和DFS O(n)。

然而，根据输入数组A，B和C的接近排序，树可能会变得不平衡，使O(n.log2(n))变得过于乐观。

  • 平均时间复杂度：O(n.log2(n))
  • 最糟糕的情况：O(n^2)
  • 空间复杂性：O(n)

Solution B - O(n.log2(n))

它基本上与以前的方法相同，不同之处在于我们首先对数组进行排序A，B和C，创建一个长度为3.n的辅助数组，其元素使用与前一解决方案类似的颜色进行装饰，并使用以下值填充此数组： A，B和C然后遍历数组并传递计算我们感兴趣的颜色过渡的数量。

sort(A);
sort(B);
sort(C);

// Constructing guards, loose syntax
int[] A' = A + { Integer.MIN_VALUE };
int[] B' = B + { Integer.MIN_VALUE };
int[] C' = C + { Integer.MIN_VALUE };

int[] D = new int[3 * n];
int i, j, k = 0;

for (int t = 0; t < 3 * n; ++t) {
   if (A'[i] >= B'[j] && A'[i] >= C'[k]) {
      D[t] = new Node(A'[i++], Amber);
   }
   else if (B'[j] >= A'[i] && B'[j] >= C'[k]) {
      D[t] = new Node(B'[j++], Blue);
   }
   else if (C'[k] >= A'[i] && C'[k] >= B'[j]) {
      D[t] = new Node(C'[k++], Cyan);
   }
}

int cyans, cyanThenBlues, solutions = 0;
for (int t = 0; t < 3 * n; ++t) {
   cyans += D[t].color() == Cyan ? 1 : 0;
   blues += D[t].color() == cyanThenBlues ? cyans : 0;
   solutions += D[t].color() == Amber ? cyanThenBlues : 0;
}

假设我们使用快速排序：

  • 平均时间复杂度：O(n.log2(n))
  • 最糟糕的情况：O(n^2)
  • 空间复杂性：O(n)

请注意，第二个解决方案的内存占用量将小于第一个解决方案的内存占用量（BST的成本）。

后续评论

  • 假设数组已排序，Theta(n)是可实现的最佳时间复杂度（因为每个元素需要至少读取一次）。这些解决方案的总体时间复杂度主要取决于BST的分类或构造。
  • 在这两种情况下，关键是展示跨越所有三个阵列的排序关系。
  • 我们能想到整数数组的另一个sorting algorithm吗？
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.