1

让我们以这个数组为例

ar = [6,3,5,1,2]

我想将它转换为另一个数组，我可能只使用两个操作 - 在特定位置插入项目（splice（i，0，item））或从特定位置删除项目（splice（i，1））。我正在寻找使用最少数量的接头的解决方案。

第二个重要条件是我们考虑具有唯一值的数组，我们的数组不包含双精度数。

例如，

ar1 = [6,3,10,5,1,2];
ar2 = [6,3,1,2,5];

很明显，如果我们想从 ar 中得到 ar1，我们只需要一个拼接 - ar.splice(2,0,10)。如果我们想得到ar2，我们必须做两次拼接：ar.splice(2,1)然后push(5)（第二个等于splice(ar.length,0,5)）

顺便说一句，这个任务自然具有实用价值。例如，让我们想象一下产品列表和产品过滤器。我们改变过滤器的设置和列表分别改变。并且每一个变化都伴随着美丽的jquery慢速向上滑动-向下滑动动画。此动画可能会向上滑动并隐藏特定项目或插入并向下滑动一个新项目。任务是减少这些动画的数量。这意味着我们试图最小化列表的 DOM 操作数量。

4

2 回答 2

2

操作数正好是编辑距离（如果您不允许替换）。查找 levenshtein 距离。

您可以修改算法以计算 levenshtein 距离以实际输出所需的操作。

于 2013-03-21T11:25:30.253 回答
1

我已经编写了希望解决问题的代码。此代码以某种方式基于 Levenshtein 距离概念。正如 maniek 的回答中提到的，这似乎对这个问题非常有用。
为简单起见，我使用字符串而不是数组并使用 Python。
对于由同一组整数组成的两个相等长度的数组，原始问题似乎很容易简化为相同的问题。因此，我假设初始字符串和目标字符串具有相同的长度并且由相同的字符集组成。
Python代码：

import random
# Create random initial (strin) and target (strout) strings
s = "abcdefghijklmnopqrstuvwxyz"
l = list(s)
random.shuffle(l)
strout = ''.join(l)
random.shuffle(l)
strin = ''.join(l)

# Use it for tests
#strin = "63125798"
#strout = "63512897"

print strin, strout

ins_del = 0
for i in xrange(len(strin)-1, -1, -1):
    if strin[i] != strout[i]:
        if strin[i-1] == strout[i]:
            ii = strout.find(strin[i], 0, i)
            strin = strin[:ii] + strin[i] + strin[ii:i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "1:", strin
        else:
            ii = strin.find(strout[i], 0, i-1)
            strin = strin[:ii] + strin[ii+1:i+1] + strout[i] + strin[i+1:]
            ins_del = ins_del + 1
            #Test output
            print "2:", strin

print strin, strout

# Check the result
for i in xrange(0, len(strin)):
    if strin[i] != strout[i]:
        print "error in", i, "-th symbol"

print "Insert/Delite operations = ", ins_del

输出示例：

kewlciprdhfmovgyjbtazqusxn qjockmigphbuaztelwvfrsdnxy
2: kewlciprdhfmovgjbtazqusxny
1: kewlciprdhfmovgjbtazqusnxy
2: kewlciprhfmovgjbtazqusdnxy
2: kewlciphfmovgjbtazqursdnxy
2: kewlciphmovgjbtazqufrsdnxy
2: kewlciphmogjbtazquvfrsdnxy
2: kelciphmogjbtazquwvfrsdnxy
2: keciphmogjbtazqulwvfrsdnxy
2: kciphmogjbtazquelwvfrsdnxy
2: kciphmogjbazqutelwvfrsdnxy
2: kciphmogjbaquztelwvfrsdnxy
2: kciphmogjbquaztelwvfrsdnxy
1: qkciphmogjbuaztelwvfrsdnxy
2: qkcipmogjhbuaztelwvfrsdnxy
2: qkcimogjphbuaztelwvfrsdnxy
1: qjkcimogphbuaztelwvfrsdnxy
2: qjkcmoigphbuaztelwvfrsdnxy
1: qjokcmigphbuaztelwvfrsdnxy
1: qjockmigphbuaztelwvfrsdnxy
qjockmigphbuaztelwvfrsdnxy qjockmigphbuaztelwvfrsdnxy
Insert/Delite operations =  19
于 2013-03-22T03:58:40.857 回答