0

问题陈述：在“n”个减少后找到给定列表中唯一数字的最小（最少）个数

输入：

N and an Array(or list)

Where 0 < N < len(Array)

N 是可能的减少数，数组的输入需要用逗号（，）分隔

示例 1：

N = 2

Array = 1, 2, 3, 3, 4, 4

输出：在删除 Array 中的 N 个元素后，查找 Least 或 minimum 个唯一元素

在上面的例子中，从数组中删除 N = 2 个元素后

在上面的例子中 1, 2 应该从数组中删除 3, 3, 4, 4 将剩余 所以，从数组中删除 2 个元素后剩余 2 个唯一元素

所以，输出应该是2

示例 2：

N = 2 [ number of reductions possible]

Input Array : 1,3,4,1,2,4,2,2 

Output: 3 [least number of unique elements]

解释：[1,1,2,2,4,4] 将是删除 [2,3] 时的结果数组

应该只用 Python 编码，但任何语言的解决方案都会受到赞赏。

4

3 回答 3

3

找到最小数量的唯一元素等同于找到最大数量的重复项。

这里的驱动想法是使用您的减少来首先取出出现次数最少的元素。为此，您需要计算列表中每个元素的出现次数，按出现次数对它们进行排序，然后从最少到最多删除它们，直到用完删除为止。唯一棘手的部分是第一部分，只有当你必须用纯 python 编写它时（@DerekLangley 的回答给出了一个很好的例子来说明你如何做到这一点）。

如果允许您导入标准库的其他部分，则collections.Counter可以快速解决此问题。这是一个示例实现，它不考虑任何可能出错的事情（例如空列表或N大于len(lst)- 这些是面试官希望您提及并知道如何处理的事情，因此请继续努力）。

import collections
...
def min_uniques(N, lst):
    # use collections.Counter to get a sorted list of unique elements and their frequencies
    most_common = collections.Counter(lst).most_common()
    # returns [(most_frequent, num_occurrences), ...], so we pull from the back to get fewest occurrences.
    # We could reverse the list and pull from the front but that would be less efficient
    while N >= most_common[-1][1]:
        # remove the element with lowest count and subtract its count from N, all at once
        N -= most_common.pop()[1] 
    # return the number of unique elements left, after we can no longer remove enough to decrease that count
    return len(most_common)

min_uniques(2, [1, 2, 3, 3, 4, 4])
# 2
min_uniques(2, [1, 3, 4, 1, 2, 4, 2, 2])
# 3

我对该代码的评论代表了我在编写代码时将如何与面试官讨论问题。这是一个四行 python 函数，但我很确定你也可以分两行来做——面试官可能会问你如何改进这段代码，如果你能把它作为一个例子（也许说“我认为它会使用机制 X 或机制 Y，但我必须先查看文档并进行一些修改）。

我并不特别了解动态编程与这里的相关性，尽管我觉得动态编程无论如何都是一个流行词。

于 2019-07-19T18:32:47.327 回答
2

由于您没有显示自己的任何代码，因此我将仅提供一些算法的想法。如果您想了解更多详细信息，请显示一些您自己的代码。

Python标准库模块中的Counter对象collections可以统计数组中每个数字出现的次数。用于Counter为您的阵列执行此操作。结果Counter对象的大小是数组中唯一项的数量。

然后使用Counter'smost_common方法将该信息从最流行的数字排序到最不流行的数字。现在看看最不受欢迎的结果。使用您的值N“删除”数组中最不受欢迎的值。您不需要实际进行删除——只需在概念上进行即可。当您完成移除（概念上或实际上）时，Counter对象的大小就是您的答案。

当然，有一些方法可以做到这一点，Counter但代码会更冗长。再一次，展示你自己的更多努力，然后我很乐意提供更多细节。

于 2019-07-19T18:30:01.023 回答
0

这是一种（可能）效率低下的方法。

ls = [1,3,4,1,2,4,2,2]
d = {}
for i in ls:
    if i not in d:
        d[i] = 1
    else:
        d[i] += 1
def min_num(n):
    counter = n
    while counter > 0:
        del d[min(d, key = d.get)]
        counter -= 1
    return len(d.keys())
min_num(2)
于 2019-07-19T18:38:14.130 回答