若覆盖0-9则约简整数

Question

在c#中对整数数组(可能更好地将它们作为字符串处理)执行以下操作的最佳解决方案是什么：

示例1:

数组由以下内容组成：

440 - 441 - 442 - 443 - 444 - 445 - 446 - 447 - 448 - 449 - 51 - 9876

其结果应是：

44 - 51 - 9876 

将规则441至449替换为44，因为我们有0-9的完整集。

示例2

数组由以下内容组成：

440 - 441 - 442 - 443 - 444 - 445 - 446 - 447 - 448 - 449 - 40 - 41 - 42 - 43 - 45 - 46 - 47 - 48 - 49

其结果应是：

4 - 51 - 9876 

应用规则:首先，3个字符串(所有以44开头的字符串)减少到44，然后相同的规则将40到49减少到4。

Answer 1

懒散地使用LINQ怎么样？

int[] arr1 = { 440, 441, 442, 443, 444, 445, 446, 447, 448, 449, 51, 9876 };

// This is just one reduction step, you would need loop over it until
// no more reduction is possible.
var r = arr1.GroupBy(g => g / 10).
        SelectMany(s => s.Count() == 10 ? new int[] {s.Key} : s.AsEnumerable());

Answer 2

这里有一个解决方案，它使用已排序的数据结构，但保存一些排序

伪码：

numbers //your array of number
sortedSet //a sorted data structure initially empty

function insertSorted (number) {
  sortedSet.put(number) //simply add the number into a sorted structure
  prefix = number / 10 //prefix should be int to truncate the number

  for (i=0;i<10;i++){
    if ( ! sortedSet contains (prefix * 10 + i) )
      break; //so i != 10, not all 0-9 occurrences of a prefix found
  }
  if ( i== 10 ) {//all occurrences of a prefix found
    for (i=0;i<10;i++){
      sortedSet remove (prefix*10 + i)
    }
    insertSorted(prefix) //recursively check if the new insertion triggered further collapses
  }
}

最后，我要以这样的方式呼吁：

foreach number in numbers
  insertSorted (number)

Answer 3

创建一个十分支索引树，记录每个节点的子节点数.然后浏览树，停在子编号为10的节点处。