3

我不确定如何组合两个整数列表中的项目，以便保留项目的顺序，并且结果列表（如果连接成一个整数）尽可能小。

可能类似于这个问题，尽管给出的答案没有解决我的大小限制： Interleave different length lists, elimating duplicates and preserve order in Python

例如，给定：

a = [3,4,5,7,9,2]
b = [3,5,7,4,2,8]

这两个列表的最短可能组合是：

c = [3,4,5,7,4,9,2,8]

连接整数值为 34574928

在某些情况下，数字的顺序不会影响列表长度，但会影响连接整数的大小。在给出的示例中，可以交换 4 和 9，同时仍保持项目的顺序，但最终数字会比必要的大。

进一步澄清：

最终列表必须包含两个原始列表中每个数字的每个实例。为了更好地表示上述示例中两者的组合：

a = [3,4,5,7,  9,2  ]
b = [3,  5,7,4,  2,8]
c = [3,4,5,7,4,9,2,8]

当然，它不会总是那么干净。在这种情况下，两个列表（3、5、7 和 2）中的四个数字可以完全合并。如果不创建更大的列表，则无法组合其中的四个数字（4、4、9 和 8）。例如：

a =     [3,    4,5,7,  9,2]
b =     [3,5,7,4,  2,8    ]
bad_c = [3,5,7,4,9,2,8,9,2]

在这种情况下，我只组合了 3 和 4 之一。当连接这两个示例结果中的项目时，我们得到：

c =     34574928
bad_c = 357492892

它们都满足排序要求，但是因为有一个不同的结果满足排序要求但在连接成整数时小于 bad_c，所以 bad_c 是不正确的结果。

4

2 回答 2

1

这是一个我认为可行的简单算法，实现相当简单，所以我不发布它。

1.对于列表，找到第一个共同的元素，收集之前的元素说两个列表是：a & b

2.一个。如果没有共同的元素，则通过比较第一个元素然后增加较小列表的索引并进行比较来合并它们。你明白了！

2. 乙。那么不失一般性，如果我们说a[3]匹配b[4]，然后将a[0]-a[2]和b[0]-b[3]一起收集，然后使用case合并这7个item它们没有任何共同元素，并在末尾附加 a[3] 的值。

3. 类似地这样做直到列表的末尾。在最后一个附加项目之后，合并剩余项目。

4. 为此，我们可以编写一个函数，从两个列表中获取要合并的子列表的开始和结束索引。

我希望这个解决方案有效，它看起来是正确的，但我还没有尝试过。如果我错过了什么，请指出。

于 2014-06-03T18:27:50.640 回答
1

这是一个相当长但正确的（据我从问题讨论中得知）使用递归的实现。

要点：

  • 我使用.pop(index). 这让我可以使用递归，因为随着函数的递归，两个列表都变得越来越小，导致一个列表是len(0).
  • 可以从任一列表中选择数字，并且可以从单个列表中连续选择的数字没有限制。
  • 不允许连续重复。
  • 比较两个不相等的数字时，较小的数字总是排在较大的位置。23xxx 总是低于 32xxx。

基本上，如果我有类似的东西[1,2,3]then [6,0,4]，第一个列表中的所有数字都将在第二个列表中的第一个数字之前，因为 1236xx总是小于 6xxxxx，1236xx 小于 16xxxx，1236xx 小于 126xxx，不管为 x 选择的值。

z = [None]
#set to None so that z[-1] doesn't throw an out-of-range error

def small_list(a,b): #recursive function

    ### BASE CASE ###

    if len(a) == 0: #if one list empty, can only add rest of other list
        for i in b:
            if i != z[-1]: #account for duplicates
                z.append(i)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    elif len(b) == 0: #if one list empty, can only add rest of other list
        for j in a:
            if j != z[-1]:#account for duplicates
                z.append(j)
            # else: #don't add duplicates

        return z.pop(0) #end recursion, remove extraneous None

    #Otherwise, we need to check whichever is smaller.  
    #The smaller number should ALWAYS go in the larger place (tens,hundreds,etc.) to make a smaller number.

    ### RECURSIVE CASE ###

    if a[0] < b[0]:
        if a[0] != z[-1]:
            z.append(a.pop(0))
        else:
            a.pop(0)
    elif a[0] > b[0]:
        if b[0] != z[-1]:
            z.append(b.pop(0))
        else:
            b.pop(0)
    elif a[0] == b[0]:
        a.pop(0)

    small_list(a,b) # recur

例子：

z = [None]

l1 = [1,2,3,2]
l2 = [2,1,1,1]

small_list(l1,l2)
print z

这第一个示例打印现在[1, 2, 1, 3, 2]是正确的。

z = [None]

l1 = [1,2,3]
l2 = [4,5,6]

small_list(l1,l2)
print z

这第二个示例打印现在[1, 2, 3, 4, 5, 6]也是正确的。

以下是它如何计算您上面给出的示例的流程：

# The format is: [final list]  len(a)  [list a]  len(b)  [list b]

[] len(a) = 6 [3, 4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# 3 repeated, so remove it.
[] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 6 [3, 5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 3), and remove from corresponding list
[3] len(a) = 5 [4, 5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (4 v 5), and remove from corresponding list
[3, 4] len(a) = 4 [5, 7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# 5 repeated, so remove it.
[3, 4] len(a) = 3 [7, 9, 2] len(b) = 5 [5, 7, 4, 2, 8]
# add lower of first two indices to final (7 v 5), and remove from corresponding list
[3, 4, 5] len(a) = 3 [7, 9, 2] len(b) = 4 [7, 4, 2, 8]
# 7 repeated, so remove it.
[3, 4, 5] len(a) = 2 [9, 2] len(b) = 4 [7, 4, 2, 8]
# add lower of first two indices to final (9 v 7), and remove from corresponding list
[3, 4, 5, 7] len(a) = 2 [9, 2] len(b) = 3 [4, 2, 8]
# add lower of first two indices to final (9 v 4), and remove from corresponding list
[3, 4, 5, 7, 4] len(a) = 2 [9, 2] len(b) = 2 [2, 8]
# add lower of first two indices to final (9 v 2), and remove from corresponding list
[3, 4, 5, 7, 4, 2] len(a) = 2 [9, 2] len(b) = 1 [8]
# add lower of first two indices to final (9 v 8), and remove from corresponding list
[3, 4, 5, 7, 4, 2, 8] len(a) = 2 [9, 2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)
[3, 4, 5, 7, 4, 2, 8, 9] len(a) = 1 [2] len(b) = 0 []
# list b is empty, add first element of list a (if non-duplicate)

#Finally:
[3, 4, 5, 7, 4, 2, 8, 9, 2]
于 2014-04-18T20:12:36.287 回答