查找給定範圍之間的最大相似數字

如果< = 10 * b且b < = 10 * a，則兩個數字（a，b）被認爲是相似的。現在給出兩個範圍低和高，返回包含給定範圍之間最大不包含非相似數字的集合。查找給定範圍之間的最大相似數字

我只能想到蠻力的方法。只需要想法如何以更好的複雜性解決這個問題。

2013-03-06 Algorithmist

你能改正/改寫你的文章並觀看你的語法嗎？真的很難得到你的意思。 – marsze 2013-03-06 09:28:17

@marsze問題明確陳述..什麼是不清楚給你 – Algorithmist 2013-03-06 09:46:34

我不明白這句話「返回包含最大數量的非相似數字在給定範圍之間的集合」您能否闡述或舉例？ – Kunukn 2013-03-06 13:41:12

從你的描述中我看到兩個數字是相似的，如果它們中較大的一個不比小的大10倍。因此，如果您想從範圍[low ... high]中找到最大數字集合，以便該集合中沒有兩個數字相似，則解決方案將從範圍中的最小數字開始，即從「low」開始，並且每次取與該集合中任何數字不相似的下一個最小數字（或者如果您只是檢查它是否與該集合中的最大元素不相似），則該數字與之相同。

算法：

採取低，然後10 *低+ 1，10 *（10 *低+ 1）+ 1等...直到它超過高限制。

來源

2013-03-06 09:46:56 aram90

可以解釋這個答案背後的邏輯。爲什麼它總是從低位開始。 – Algorithmist 2013-03-06 09:56:54

它不一定要從低處開始，但是對於人來說更容易理解/更加自然地向上計數。您也可以通過以下方式解決：取*高*，然後*高/ 10 - 1 *，* ans/10 - 1 *等，直到下一個計算答案低於*低*限。 – deed02392 2013-03-06 10:06:36

當然，有趣的是證明/反駁你得到相同數量的元素，無論你是從低位還是高位開始;） – us2012 2013-03-06 10:10:00

如果我理解正確的問題，這應該工作：

// 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; 
}

後一種方法也許可以找到更多的數字，比第一個，試試吧。但是，可能總是會有不同組的不相似的數字，並且可能具有相同的大小。

來源

2013-03-06 10:04:46 marsze

查找給定範圍之間的最大相似數字

回答

相關問題