给定一组最佳拟合尺寸,告诉其他阵列可以安装多少个元素(下面有更多详细信息)

Question

有一个旧的干井.它的侧面由混凝土环制成.每个这样的环都是一米高,但环可以具有不同的(内部)直径.然而,所有环都相互对中.井深N米; 也就是说,里面有N个混凝土环.您将要将M具体磁盘放入井中.每个磁盘厚一米,不同的磁盘可以有不同的直径.一旦每个磁盘都被丢弃,它就会掉下来,直到:

• 它击中井底;
• 它击中一个内径小于圆盘直径的环; 要么
• 它击中了之前丢弃的磁盘.(请注意,如果环的内径和磁盘的直径相等,则磁盘可能会从环中掉落.)

您准备放下的磁盘已准备就绪,您可以知道它们的直径以及井中所有环的直径.问题出现了:有多少磁盘适合井？

写一个函数:int falling_disks(int A [],int N,int B [],int M); 给定两个零索引的整数数组--A,包含N个环的内径(自上而下的顺序),和B,包含M个磁盘的直径(按它们要被丢弃的顺序) - 返回适合井的磁盘数.例如,给定以下两个数组:

      A[0] = 5    B[0] = 2
      A[1] = 6    B[1] = 3
      A[2] = 4    B[2] = 5
      A[3] = 3    B[3] = 2
      A[4] = 6    B[4] = 4
      A[5] = 2
      A[6] = 3

该函数应该返回4,因为除了最后一个磁盘之外的所有磁盘都将适合井.该图显示了丢弃四个磁盘后的情况.

假使,假设:

• N是[1..200,000]范围内的整数;
  • M是[1..200,000]范围内的整数;
  • 数组A的每个元素是[1..1,000,000,000]范围内的整数;
  • 数组B的每个元素是[1..1,000,000,000]范围内的整数.

复杂:

• 预期的最坏情况时间复杂度是O(N);
  • 预期的最坏情况空间复杂度是O(N),超出输入存储(不计入输入参数所需的存储).
  • 可以修改输入数组的元素.

我尝试使用堆栈并做一些事情,但我无法进入O(n)解决方案,即使经过一些优化,我认为最坏的情况仍然是O(n ^ 2).

Answer 1

首先,您需要修改环的给定内径以填补不必要的间隙.假设您的内径5环低于内径环2.任何大小超过的磁盘2都无法到达该环.所以我们可以将下环的内径改为2.基本上我们正在填补空白.

之前:

后:

使用以下算法:

1. min = A [0]
2. i = 1
3. 如果我= = N然后停止
4. 如果A [i] <min则min = A [i]
5. 如果A [i]> min则A [i] = min
6. 我++
7. 转到第3步

既然环已形成一种结构,其中每个下环的内径小于或等于上环的内径,则下一部分相当简单.我们将从底部开始插入磁盘.如果第一个圆盘适合最低的环,那么就好了,否则我们会移动到它上面的环上,依此类推.您可以使用如下算法:

1. i = N-1
2. j = 0
3. 如果i <0或j == M则停止
4. 如果A [i]> = B [j]那么j ++
5. 一世 -
6. 转到第3步

变量的最终值j是必需的答案.

Answer 2

public static int falling_disks(int[] A, int[] B)
{
    int mymin = A[0];
    int nbDisk = 0;

    for (int i = 0; i < A.Length; i++)
    {
        if (A[i] < mymin) mymin = A[i];
        if (A[i] > mymin) A[i] = mymin;               
    }             

    for (int i = A.Length - 1; i >= 0; i--) 
    {
        if (B[nbDisk] <= A[i]) nbDisk++;
        if (nbDisk == B.Length) break;
    }           

    return nbDisk;
 }