连续数字分组算法

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

目前，我不确定如何处理最后一种情况，但是看这个算法，它似乎不太高效。有更好/更容易的方法来排序这组数字吗？

- Adjit

---

我会在循环后面加一个检查来处理关闭最后一个范围。 - juharr

我建议您创建一个哈希集合来存储您的邮政编码，而不是创建一个列表并调整范围，然后使用Contains方法来检查给定的邮政编码是否存在于集合中。HashSet.Contains非常高效。 - sschimmel

这些邮政编码是否总是按递增顺序排列？如果是，解决方案相当简单-您只需遍历它们并找出范围即可。如果不是，则使用哈希表或二进制数组。 - Огњен Шобајић

正如@ОгњенШобајић所提到的，如果代码已经排序，那么解决方案的时间复杂度是O(n)。 - vgru

Answer 1

这里提供了一个 O(n) 的解决方案，即使你的邮政编码没有保证按顺序排列。

如果您需要输出分组进行排序，则不能比 O(n*log(n)) 更好，因为您必须对某些内容进行排序，但如果仅关注分组邮政编码而不需要对组进行排序，则可以使用此算法。它充分利用了 HashSet、字典和DoublyLinkedList。据我所知，该算法的时间复杂度为 O(n)，因为我相信 HashSet.Add() 和 HashSet.Contains() 的时间复杂度是常数级别的。

这里有一个可工作的 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))算法会更简单，因为一旦对输入列表进行排序，组可以在一次迭代中形成，并且不需要任何额外的数据结构。

- Frank Bryce

---

从来没有想过使用哈希表。谢谢。 - Adjit

Answer 2

我相信你在这个问题上想太多了。只需使用Linq对IEnumerable进行搜索，就可以在不到1/10秒的时间内搜索80,000条记录。

我使用了这里的免费CSV邮政编码列表：http://federalgovernmentzipcodes.us/free-zipcode-database.csv

using System;
using System.IO;
using System.Collections.Generic;
using System.Data;
using System.Data.OleDb;
using System.Linq;
using System.Text;

namespace ZipCodeSearchTest
{
    struct zipCodeEntry
    {
        public string ZipCode { get; set; }
        public string City { get; set; }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<zipCodeEntry> zipCodes = new List<zipCodeEntry>();

            string dataFileName = "free-zipcode-database.csv";
            using (FileStream fs = new FileStream(dataFileName, FileMode.Open, FileAccess.Read))
            using (StreamReader sr = new StreamReader(fs))
                while (!sr.EndOfStream)
                {
                    string line = sr.ReadLine();
                    string[] lineVals = line.Split(',');
                    zipCodes.Add(new zipCodeEntry { ZipCode = lineVals[1].Trim(' ', '\"'), City = lineVals[3].Trim(' ', '\"') });
                }

            bool terminate = false;
            while (!terminate)
            {
                Console.WriteLine("Enter zip code:");
                var userEntry = Console.ReadLine();
                if (userEntry.ToLower() == "x" || userEntry.ToString() == "q")
                    terminate = true;
                else
                {
                    DateTime dtStart = DateTime.Now;
                    foreach (var arrayVal in zipCodes.Where(z => z.ZipCode == userEntry.PadLeft(5, '0')))
                        Console.WriteLine(string.Format("ZipCode: {0}", arrayVal.ZipCode).PadRight(20, ' ') + string.Format("City: {0}", arrayVal.City));
                    DateTime dtStop = DateTime.Now;
                    Console.WriteLine();
                    Console.WriteLine("Lookup time: {0}", dtStop.Subtract(dtStart).ToString());
                    Console.WriteLine("\n\n");
                }
            }
        }
    }
}

- Mike U

Answer 3

在这种特殊情况下，使用哈希可能会更快。然而，基于范围的解决方案将使用更少的内存，所以如果您的列表非常大（我并不确定是否有足够多的可能的邮政编码使得任何一个邮政编码列表都足够大），那么使用基于范围的解决方案是合适的。

无论如何，以下是一个更简单的逻辑来创建范围列表并查找目标是否在范围内：

1. 将`ranges`作为一个简单的整数列表（甚至是邮政编码列表），并将`zip`的第一个元素添加为它的第一个元素。 2. 对于除最后一个元素之外的`zip`的每个元素，如果该元素加一不等于下一个元素，则将该元素加一和下一个元素都添加到`ranges`中。 3. 在`ranges`的末尾添加比`zip`的最后一个元素多一的值。

现在，要查找一个邮政编码是否在ranges中，请对ranges进行二分搜索，以查找大于目标邮政编码的最小元素。[注1]如果该元素的索引是奇数，则目标位于其中一个范围内，否则不在其中。

---

注：

据我所知，在 C# 列表上使用 BinarySearch 方法会返回找到的元素的索引或第一个较大元素的索引的补码。为了获得建议算法所需的结果，您可以使用类似于 index >= 0 ? index + 1 : ~index 的东西，但是更简单的方法可能是搜索目标值减一的邮政编码，然后使用结果的低位比特的补码。

- rici