1

全部，

我需要一种聪明的方法来尽可能快速和干净地实现这个算法（工作）：我想我已经删除了所有语言特定的问题并将其归结为：

我有两个数组：A 和 B。

A 中有一个名称列表 {Apple, Apple, Banana, Banana, Banana, Carrot, ...} 每个第 i 个值在 A 中出现的次数没有上限。可以只有一个“苹果”或数不胜数。

A 中的每个条目在 B 中都有一个匹配的条目。（多对多映射）。例如：

A[0] = "Apple"      B[0] = "0027"
A[1] = "Apple"      B[1] = "0028"
A[2] = "Banana"     B[2] = "0073"
A[3] = "Banana"     B[3] = "0041"
A[4] = "Banana"     B[4] = "0069"

如果 A 中有 100 个或更少的条目实例（如果有 <= 100 个香蕉），那么它们必须共享相同的初始“B”值。如果超过 100 个，则前 100 个必须共享相同的 B 值，但接下来的 100 个将具有第 B[i + 100] 个值。

例如，如果有 102 个苹果

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0028"
...
A[99]  = "Apple"       B[99]  = "0073"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0069"
A[102] = "Banana"      B[102] = "0123"

那么我想要的结果是这样的：

A[0]   = "Apple"       B[0]   = "0027"
A[1]   = "Apple"       B[1]   = "0027"
...
A[99]  = "Apple"       B[99]  = "0027"
A[100] = "Apple"       B[100] = "0041"
A[101] = "Apple"       B[101] = "0041"
A[102] = "Banana"      B[102] = "0123"

我敢肯定有一些超级大脑可以想出我设计的蹩脚算法，所以让我们看看吧！

编辑1：我想我应该指出这是为了工作。我认为这是一个有趣的挑战，有人可能想看看，并且可能想出比我想出的更好的解决方案。

编辑2：感谢丹尼尔指出我的愚蠢错误。

我的解决方案只是为了比较（伪代码）：

首先制作 B 的哈希/字典，称为 d，其中 d[ "Apple" ] = A 中 Apple 的实例数。

while (i < A.count)
{
    string cmp = A[i];
    int v = d[cmp];
    int j=i;

    while (v--) {
       B[j++] = B[i];

       if (j %100 == 0)
       i += j
    }
    i+= d[cmp];
}

从记忆中做到这一点，希望我没有搞砸索引......

4

4 回答 4

2

就我理解问题并假设数组已排序而言，我在 C# 中的建议。

String[] A = GetAs();
String[] B = GetBs();

Int32 count = 0;
Int32 index = 1;

while (index < A.Length)
{
   if (A[index] != A[index - 1])
   {
      count = 0;
   }

   currentCount++;

   if ((A[index] == A[index - 1]) && (count % 100 != 1))
   {
      B[index] = B[index - 1];
   }

   index++;
}

如果有人喜欢它紧凑（和从零开始的计数）。

String[] A = GetAs();
String[] B = GetBs();

Int32 c = 0, i = 1;

while (i < A.Length)
{
   c = (A[i] == A[i - 1]) ? c + 1 : 0;

   B[i] = ((A[i] == A[i - 1]) && (c % 100 != 0)) ? B[i - 1] : B[i];

   i++;
}
于 2009-09-04T13:00:02.230 回答
0

我想建立一个字典/哈希表，比如

{'Apple':
    {'NumberSeen':102,
     'BValues':['0027','0041']
    },
 'Banana':
    {'NumberSeen':1,
     'BValues':['0123']
    }
}

然后你循环这个，如果 NumberSeen%100 = 1 添加一个新的 b 值，然后从这个字典重新创建 B 数组。

编辑：这为您提供了一个处理未排序列表的可读解决方案。我刚刚看到您的“列表已排序”评论，这意味着您可以在 O(1) 空间中更简单地执行此操作，但我不确定代码的清晰程度。

于 2009-09-04T12:59:47.503 回答
0 
String curFruit = A[0];
int curFruitCount = 0;
for (int i = 1; i < A.length; i++) {
    if (A[i].equals(curFruit) && curFruitCount < 100) {
        B[i] = B[i-1];
        curFruitCount++;
    }else{
        curFruit = A[i];
        curFruitCount = 1;
    }
}
于 2009-09-04T13:05:18.653 回答
0

我真的很喜欢 Daniel Brückner 的解决方案，但我认为您也许可以对其进行改进。假设 'A's 被排序并且 100 个连续相同的水果是常见的，那么你可以通过添加以下检查来利用它：

String[] A = GetAs();
String[] B = GetBs();
Int32 c = 0, i = 1;
while (i < A.Length)
{   
    if(i+99 < A.Length && A[i] == A[i+99])
    {
        for(int j=1;j<100;j++) b[i+j] = b[i];

        i = i+99;
    }
    else
    {
        B[i] = (A[i] == A[i - 1]) ? B[i - 1] : B[i];   
        i++;
    }
}
于 2009-09-04T14:31:24.197 回答