c# - 对连续数字进行分组的算法

Question

我正在尝试构建一个高效的算法来处理包含客户邮政编码的数千行数据。然后我想将这些邮政编码与大约 1000 个邮政编码的分组进行交叉检查，但我有大约 100 列 1000 个邮政编码。很多邮政编码都是连续的数字，但也有很多随机的邮政编码。所以我想做的是将连续的邮政编码组合在一起，然后我可以检查邮政编码是否在该范围内，而不是针对每个邮政编码进行检查。

示例数据-

90001
90002
90003
90004
90005
90006
90007
90008
90009
90010
90012
90022
90031
90032
90033
90034
90041

这应该按如下方式分组:

{ 90001-90010, 90012, 90022, 90031-90034, 90041 }

这是我对算法的想法:

public struct gRange {
   public int start, end;

   public gRange(int a, int b) {
      start = a;
      if(b != null) end = b;
      else end = a;
   }
}

function groupZips(string[] zips){
    List<gRange> zipList = new List<gRange>();
    int currZip, prevZip, startRange, endRange;
    startRange = 0;

    bool inRange = false;

    for(int i = 1; i < zips.length; i++) {
        currZip = Convert.ToInt32(zips[i]);
        prevZip = Convert.ToInt32(zips[i-1]);

        if(currZip - prevZip == 1 && inRange == false) {
            inRange = true;
            startRange = prevZip;
            continue;
        }
        else if(currZip - prevZip == 1 && inRange == true) continue;
        else if(currZip - prevZip != 1 && inRange == true) {
            inRange = false;
            endRange = prevZip;
            zipList.add(new gRange(startRange, endRange));
            continue;
        }
        else if(currZip - prevZip != 1 && inRange == false) {
            zipList.add(new gRange(prevZip, prevZip));
        }
        //not sure how to handle the last case when i == zips.length-1
    }
}

到目前为止，我不确定如何处理最后一种情况，但看看这个算法，我觉得它的效率并不高。有没有更好/更简单的方法来对这样的一组数字进行排序？

Answer 1

这是一个O(n) 的解决方案，即使不能保证您的邮政编码是有序的。

如果你需要对输出分组进行排序，你不能比 O(n*log(n)) 做得更好，因为在某个地方你必须对某些东西进行排序，但是如果分组邮政编码是您唯一关心的问题，不需要对组进行排序，那么我会使用这样的算法。它很好地利用了 HashSet 、字典和 DoublyLinkedList .据我所知，这个算法是 O(n)，because I believe that a HashSet.Add() and HashSet.Contains() are performed in constant time .

这是一个有效的 dotnetfiddle

// I'm assuming zipcodes are ints... convert if desired
// jumbled up your sample data to show that the code would still work
var zipcodes = new List<int>
{
    90012,
    90033,
    90009,
    90001,
    90005,
    90004,
    90041,
    90008,
    90007,
    90031,
    90010,
    90002,
    90003,
    90034,
    90032,
    90006,
    90022,
};

// facilitate constant-time lookups of whether zipcodes are in your set
var zipHashSet = new HashSet<int>();

// lookup zipcode -> linked list node to remove item in constant time from the linked list
var nodeDictionary = new Dictionary<int, DoublyLinkedListNode<int>>();

// linked list for iterating and grouping your zip codes in linear time
var zipLinkedList = new DoublyLinkedList<int>();

// initialize our datastructures from the initial list
foreach (int zipcode in zipcodes)
{
    zipLinkedList.Add(zipcode);
    zipHashSet.Add(zipcode);
    nodeDictionary[zipcode] = zipLinkedList.Last;
}

// object to store the groupings (ex: "90001-90010", "90022")
var groupings = new HashSet<string>();

// iterate through the linked list, but skip nodes if we group it with a zip code
// that we found on a previous iteration of the loop
var node = zipLinkedList.First;
while (node != null)
{
    var bottomZipCode = node.Element;
    var topZipCode = bottomZipCode;

    // find the lowest zip code in this group
    while (zipHashSet.Contains(bottomZipCode - 1))
    {
        var nodeToDel = nodeDictionary[bottomZipCode - 1];

        // delete node from linked list so we don't observe any node more than once
        if (nodeToDel.Previous != null)
        {
            nodeToDel.Previous.Next = nodeToDel.Next;
        }
        if (nodeToDel.Next != null)
        {
            nodeToDel.Next.Previous = nodeToDel.Previous;
        }
        // see if previous zip code is in our group, too
        bottomZipCode--;
    }
    // get string version zip code bottom of the range
    var bottom = bottomZipCode.ToString();

    // find the highest zip code in this group
    while (zipHashSet.Contains(topZipCode + 1))
    {
        var nodeToDel = nodeDictionary[topZipCode + 1];

        // delete node from linked list so we don't observe any node more than once
        if (nodeToDel.Previous != null)
        {
            nodeToDel.Previous.Next = nodeToDel.Next;
        }
        if (nodeToDel.Next != null)
        {
            nodeToDel.Next.Previous = nodeToDel.Previous;
        }

        // see if next zip code is in our group, too
        topZipCode++;
    }

    // get string version zip code top of the range
    var top = topZipCode.ToString();

    // add grouping in correct format
    if (top == bottom)
    {
        groupings.Add(bottom);
    }
    else
    {
        groupings.Add(bottom + "-" + top);
    }

    // onward!
    node = node.Next;
}


// print results
foreach (var grouping in groupings)
{
    Console.WriteLine(grouping);
}

** 普通链表节点删除逻辑的小重构是有序的

如果需要排序

O(n*log(n)) 算法要简单得多，因为一旦您对输入列表进行排序，就可以在列表的一次迭代中形成组，而无需额外的数据结构。