推荐逻辑或算法，这个难题

问题描述：

有两个数组

Array1 {5,6,7,8}

和

Array2 {2,1,1,0}

下面是满足某一条件的图案

Here is a pattern which satisfies a certain condition

8,6,5,7

的条件：考虑到上述ARRAY2的各个元素数组1的8图案说，它具有比8到其留在图案更大的0元素，同样ARRAY2各自的元素数组1的6说它有1元大于6到它在pattern.And左等......

The Condition: Considering the pattern above Array2's respective element to Array1's 8 says that it has 0 elements greater than 8 to its left in the pattern,similarly Array2's respective element to Array1's 6 says that it has 1 element greater than 6 to the left of it in the pattern.And so on......

由于2个数组有没有办法来产生pattern.Any算法逻辑将AP preciated。

Given the 2 arrays is there a way to generate the pattern.Any algorithm logic would be appreciated.

答

下面是应该是一个算法：

Here's an algorithm that should work:

排序号。（修改：由数，然后通过左计数）
对于每个编号，提供其所需 N 较大的数字在它的左边，把它放在 N + 1 从左边个空闲插槽。
如果没有那么多无牵无挂插槽，原来的两个数组不允许这样的模式存在。

Sort the numbers. (Edit: by number and then by left-count)
For each number, given it needs n larger numbers to its left, put it in the n+1th free slot from the left.
If there aren't that many free slots left, the two original arrays don't allow such a pattern to exist.

下面是它如何工作在你的例子：

Here's how it works on your example:

开始用最小的数，5，需要在它的左边两个较大的项目。由于的所有的另一个项目是较大的，把它放在左起第三位。 _ _ _ 5
在接下来最小的是6，需要在左边的一个大项目。由于的所有的其余项目均较大，它需要去第二空闲插槽。 _ 6 5 _
在接下来最小的是7，需要在左边的一个大项目。由于的所有的其余项目均较大，它需要去第二空闲插槽。 _ 6 5 7
在接下来的8，需要在左侧没有任何较大的物品。它需要走在第一个空闲插槽。 8 6 5 7

Start with the smallest number, 5. It needs two larger items on its left. Since all the other items are larger, put it third from the left. _ _ 5 _
Next smallest is 6. It needs one larger item on the left. Since all remaining items are larger, it needs to go in the second free slot. _ 6 5 _
Next smallest is 7. It needs one larger item on the left. Since all remaining items are larger, it needs to go in the second free slot. _ 6 5 7
Next is 8. It needs no larger items on the left. It needs to go in the first free slot. 8 6 5 7

下面是一个粗略的实现在C＃：

Here's a rough implementation in 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;
}

修改：我原来的code没有正确地处理重复号码;现在这个版本应该这样做。

Edit: My original code didn't correctly handle duplicate numbers; this version now should do so.

推荐逻辑或算法，这个难题

相关推荐