删除数字的低位数字

Question

给定一个数字 n，共 x 个数字。如何删除 y 位数字，从而使剩余数字产生更大的可能数字？

示例：

1)x=7  y=3
n=7816295
  -8-6-95
         =8695

2)x=4  y=2
n=4213
  4--3
      =43

3)x=3  y=1
n=888
     =88

只是声明：x > y > 0。

Answer 1

如果 x = y 我们必须删除所有数字。

否则，您需要在前y + 1 位数字中找到最大数字。然后删除这个最大数字之前的所有 y0 元素。然后您需要将该最大值添加到答案中，然后再次重复该任务，但您现在需要删除 y - y0 个元素。

在最坏的情况下，直接实施将在 O(x^2) 时间内工作。

但是使用线段树数据结构可以有效地找到给定范围内的最大值。在最坏的情况下，时间复杂度将为 O(x * log(x))。

P. S. 我刚刚意识到，也有可能在 O(x) 中解决，使用仅存在 10 位数字的事实（但算法可能有点复杂）。我们需要找到给定范围 [L, R] 中的最小值，但此任务中的范围将从左到右 "change"（L 和 R 始终递增）。我们只需要存储 10 个指向数字的指针（每个数字 1 个）到数字中的第一个位置，使得位置 >= L。然后为了找到最小值，我们只需要检查 10 个指针。为了更新指针，我们将尝试将它们向右移动。

所以时间复杂度为O(10 * x) = O(x)

Answer 2

这是一个复杂度为 O(x) 的解决方案。它建立一个索引，将 (i, d) 映射到 j，最小的数字 > i 使得 n 的第 j 个数字是 d。使用此索引，可以轻松地在 O(1) 时间内找到解决方案中最大可能的下一位数字。

def index(digits):
    next = [len(digits)+1] * 10
    for i in xrange(len(digits), 0, -1):
        next[ord(digits[i-1])-ord('0')] = i-1
        yield next[::-1]

def minseq(n, y):
    n = str(n)
    idx = list(index(n))[::-1]
    i, r = 0, []
    for ry in xrange(len(n)-y):
        i = next(j for j in idx[i] if j <= y+ry) + 1
        r.append(n[i - 1])
    return ''.join(r)

print minseq(7816295, 3)
print minseq(4213, 2)

Answer 3

伪代码：

Number.toDigits().filter (sortedSet (Number.toDigits()). take (y))

恕我直言，您不需要知道 x。

为了效率，Number.toDigits()可以预先计算

digits = Number.toDigits()
digits.filter (sortedSet (digits).take (y))

根据语言和上下文，您要么输出数字并完成，要么必须再次将结果转换为数字。

工作 Scala-Code 例如：

def toDigits (l: Long) : List [Long] = if (l < 10) l :: Nil else (toDigits (l /10)) :+ (l % 10)

val num = 734529L
val dig = toDigits (num)
dig.filter (_ > ((dig.sorted).take(2).last))

有序集合是经过排序的集合，这意味着每个元素只包含一次，然后生成的集合按某些标准排序，例如数字升序。 => 234579。

我们从其中两个 (23) 中取出最后一个 (3) 并根据标准过滤数字，即数字必须大于该值 (3)。

你的问题没有明确说明，每个数字在原始数字中只包含一次，但由于你没有给出标准，不确定要删除哪一个，我将其视为隐含的假设。

其他语言当然可能有其他表达式（x.sorted, x.toSortedSet, new SortedSet (num), ...）或缺少某些类, 函数，你会必须自己建造。

您可能需要编写自己的过滤方法，它采用谓词 P 和集合 C，以及 returns 满足 P 的所有元素的新集合，P 是采用一个 T 的方法returns 一个布尔值。非常有用的东西。

Answer 4

对于要删除的每个数字：从左到右遍历数字；如果你发现一个数字小于它右边的数字，删除它并停止，否则删除最后一个数字。

如果位数x大于数字的实际长度，则表示有前导零。因为那些将是第一个离开的，你可以简单地减少计数 y 相应的数量。

这是 Python 中的工作版本：

def remove_digits(n, x, y):
    s = str(n)
    if len(s) > x:
        raise ValueError
    elif len(s) < x:
        y -= x - len(s)
    if y <= 0:
        return n
    for r in range(y):
        for i in range(len(s)):
            if s[i] < s[i+1:i+2]:
                break
        s = s[:i] + s[i+1:]
    return int(s)

>>> remove_digits(7816295, 7, 3)
8695
>>> remove_digits(4213, 4, 2)
43
>>> remove_digits(888, 3, 1)
88

我犹豫要不要提交这个，因为它看起来太简单了。但是我想不出它不起作用的情况。

删除数字的低位数字

Remove the inferior digits of a number

language-agnostic

algorithm