c# - 如果覆盖 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 的节点处。