开发过程中碰到的依据断号最小值插入新单据算法

开发过程中遇到的依据断号最小值插入新单据算法
  在做现在的这个产品的时候，碰到一个常见的单据插入场景。
场景描述如下：
   工厂里的一种单据，这种单据的单号(单号为字符串类型)生成须有如下的限制条件：
插入时按顺序插入，即单号生成为递增1。工人进行操作时，如遇到删除单据的情形，是随机的删除。在这时候，如果继续插入一条新单据，新单据单号满足的条件是，必须为整个单号序列中，最小连续完整序列的最大单号加1。
例如：原单号序列为：1,2,3,4,5,6,7。
（1）随机删除单号为4的单据，这个时候的序列号为1,2,3,5,6,7,如果此时插入新单据的话，最小完连续整序列为(1,2,3),新增单号为4。
（2）随机删除3,5,7，此时的序列号为1,2,4,6,如果此时插入新单据，单号应为剩余单号的最小连续完整序列(1,2)，新增单号为3。

问题其实很简单。
<1> 当然如果是很小规模的数据，完全可以直接用循环直接扫描到最小的断号。
     代码如下：

int minLackNum;if (reslut.Count != max){   for (int i = 0; i < reslut.Count; i++)   {     if (Convert.ToInt16(reslut[i][0], CultureInfo.CurrentCulture) != i + 1)      {minLackNum = i; break;      }   }}

<2>咱们的这个产品是服务于制造业的，所以里面涉及到的单据数量可能比较大，从性能角度考虑，这个地方可以设计一个比较好的算法，来降低一下复杂度。本人首先想到的变是二分查找法，利用二分查找法的衍生算法可以很快的找到断号中的最小号，这时需要插入的新单号就很容易算出。

伪码如下：
int max=20;
Array[] arr = new Array[max];
int left = 0;right = max-1;
while(left <= right){
int midd = (left+right)/2;
if(arr[midd]==midd+1){
left = midd+1;
continue;
}else if(arr[midd]==null || arr[midd] != midd+1){
right = midd -1;
continue;
}
}
return right+1;
具体C#代码：

using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace ConsoleApplication2{    class Program    {        static void Main(string[] args)        {            int[] arr = new int[] {1,2,3,4,5,6,7,9,10,11,12};            int left = 0;            int right = arr.Length - 1;                        while (left <= right)            {                Console.WriteLine("*");                int midd = (left + right) / 2;                if (arr[midd] == midd + 1)                {                    left = midd + 1;                    continue;                }                else if (arr[midd] != midd + 1)                {                    right = midd - 1;                    continue;                }                Console.WriteLine("*");            }            Console.Write(right + 2);            Console.ReadKey();        }    }}

相信这个算法基本能解决在生产中碰到的同一类问题了，不过有没有更简单的，不需要代码的方法呢？以下给出第三种解决方法，这种方法不需要代码，只用SQL就行。

<3> 给出表结构。表A,只有一个字段A_ID，nchar类型。A_ID为不连续升序列。
   

Select MIN(A_NID) from  (Select CAST(A_ID AS Int)+1 as A_NID from A) as B where A_NID not in (select A_ID from A);

使用上述SQL，可以直接求出所需单号！

以上为本人碰到这个问题的一点心得，还望各位多多指教~

查看更多 下一篇