algorithm - 查找给定范围之间的最大不同数

Question

如果 a<=10*b 和 b<=10*a ，则称两个数 (a,b) 相似。现在给定两个范围 low 和 high ，返回一个集合，其中包含给定范围之间最大数量的非相似数字。

我只能想到蛮力方法。只需要知道如何以更好的复杂性解决这个问题。

Answer 1

从您的描述中，我看到如果其中较大的数字不超过小数字的 10 倍，则两个数字是相似的。因此，如果您想从范围 [low...high] 中找到最大的数字集，以便该集合中没有两个数字相似，则解决方案将是从范围内的最小数字开始，即从“low”开始，并且每次取下一个与集合中的任何数字都不相似的最小数字（或者如果您只是检查它是否与集合中的最大元素不相似，则它是相同的）。

算法：

取low，然后10 * low + 1、10 * (10 * low + 1) + 1等...直到超过上限。

Answer 2

如果我正确理解问题，这应该有效：

// start with smallest number:

var numbers = [];
var number = range.lowest;
// while not reached end of range
while (number <= range.highest) {
    // add this number;
    numbers.push(number);
    // find next not similar number
    number = numbers * 10 + 1;
}

// start with highest number:

var numbers = [];
var number = range.highest;
// while not reached end of range
while (number >= range.lowest) {
    numbers.push(number);
    // find next non-similar number
    var newNumber = Math.floor(number / 10.0);
    if (numNumber == number / 10.0);
        newNumber--;
    number = newNumber;
}

后一种方法可能会比第一种方法找到更多的数字，试试吧。但是，可能总会有不同的不相似数集，它们的大小可能相同。