-1

有两个数组

Array1 {5,6,7,8}

和

Array2 {2,1,1,0}

这是满足特定条件的模式

8,6,5,7

条件：考虑到 Array2 的相应元素到 Array1 的 8 上方的模式表示它在模式左侧有 0 个大于 8 的元素，类似地，Array2 到 Array1 的 6 的相应元素表示它的左侧有 1 个大于 6 的元素在模式中。等等......

给定 2 个数组是否有生成模式的方法。任何算法逻辑都将不胜感激。

4

2 回答 2

3

这是一个应该有效的算法：

  • 对数字进行排序。（编辑：按数字，然后按左计数）
  • 对于每个数字，考虑到它的左边需要n更大的数字，把它放在左边的n+1第 th 个空闲槽中。
  • 如果剩下的空闲插槽不多，则两个原始数组不允许这样的模式存在。

以下是它在您的示例中的工作方式：

  • 从最小的数字 5 开始。它的左边需要两个较大的项目。由于所有其他项目都较大，所以把它从左边数第三个。_ _ 5 _
  • 下一个最小的是 6。左边需要一个较大的项目。由于所有剩余项目都较大，因此需要进入第二个空闲槽。_ 6 5 _
  • 下一个最小的是 7。它需要一个更大的项目在左边。由于所有剩余项目都较大，因此需要进入第二个空闲槽。_ 6 5 7
  • 接下来是 8。左边不需要更大的项目。它需要进入第一个空闲插槽。8 6 5 7

这是 C# 中的粗略实现：

public static int[] algorithm(int[] numbers, int[] counts)
{
    var pairs = numbers                         // EDIT:
        .Zip(counts, (n, c) => new { n, c })    // This is needed to
        .OrderBy(p => p.n)                      // correctly handle
        .ThenBy(p => p.c)                       // duplicate numbers
        .ToArray();
    int[] output = new int[pairs.Length];
    List<int> freeIndices = Enumerable.Range(0, pairs.Length).ToList();
    for (int i = 0; i < pairs.Length; i++)
    {
        if (pairs[i].c < freeIndices.Count)
        {
            int outputIndex = freeIndices[pairs[i].c];
            freeIndices.RemoveAt(pairs[i].c);
            output[outputIndex] = pairs[i].n;
        }
        else
        {
            throw new ArgumentException();
        }
    }
    return output;
}

编辑：我的原始代码没有正确处理重复的数字；这个版本现在应该这样做。

于 2012-11-20T14:45:06.207 回答
1

与其将其视为两个数组，不如将其视为 Number/LeftCount 对的单个列表。

首先只考虑 (LeftCount == 0) 的对集合。在这组中选择编号最小的一组 ( n)。

写到n屏幕上。

从列表中删除这对。

对于 Number 小于 的所有剩余对n，递减 LeftCount。

重复直到列表中没有任何对。

 

如果你理解这个算法的想法，把它编码成两个独立的数组就不会太难了。

于 2012-11-20T15:01:46.713 回答