代码之家 › 专栏 › 技术社区 › Ryan Ahearn

编写脑筋急转弯程序以更新数组(语言不可知)

code-golf puzzle algorithm

Ryan Ahearn · 技术社区 · 7 年前

所有人,

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

我有两个数组:A和B。

A中有一个名称列表{Apple,Apple,Banana,Banana,Banana,Carrot,…}第i个值对它在A中出现的次数没有上限。可能只有一个“Apple”或无数个。

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]th值。

如果有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的hash/字典,称为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 回复 | 直到 14 年前

Daniel Brückner 17 年前

我在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++;
}

Greg 17 年前

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

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

然后循环,如果numbersen%100=1,则添加一个新的b值,然后从此字典中重新创建b数组。

编辑:这将为您提供一个可读的解决方案,用于处理未排序的列表。我刚刚看到你的“list is sorted”注释,这意味着你可以在O(1)空间中做得更简单,但我不确定代码会有多清晰。

Alex Spurling danprice 17 年前

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;
    }
}

LJM Tim Schmelter 17 年前

我真的很喜欢丹尼尔布克纳的解决方案,但我想你可以做一个改进。假设“A”被分类,并且连续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++;
    }
}