c# - 需要对复杂的物体进行排序，例如多米诺骨牌

Question

这是一种情况。例如我有这样的结构(代码已简化):

class Dominoe 
{
    ctor Dominoe(left, right)        

    string LeftSide;
    string RightSide;
}

我有数据，有点像这样:

Dominoe("2", "3"), Dominoe("1", "2"), Dominoe("4", "5"), Dominoe("3", "4")

我知道多米诺骨牌上不会有任何间隙，也不会有重复。 我需要订购这个集合，因此每个 RightSide 都将连接到适当的 LeftSide。就像这样:

Dominoe("1", "2"), Dominoe("2", "3"), Dominoe("3", "4"), Dominoe("4", "5")

值 - 而不是数字。只需要一个线索。

现在我已经通过两步完成了这项任务。主要 - 我正在寻找切入点。具有左侧的多米诺骨牌不会出现在任何其他多米诺骨牌右侧。之后我用 0 索引项切换它。其次 - 我正在寻找下一个多米诺骨牌，其左侧与我的条目多米诺骨牌的右侧相同，依此类推。

我在 C# 中执行此操作，但这并不重要。

问题是 - 我不认为这是最好的算法。任何想法都会很棒。谢谢。

已编辑!

谈论数字是我的错吗？

让我们将多米诺骨牌改为旅行卡。

所以它会像:

TravelCard ("Dublin", "New York"), TravelCard ("Moscow", "Dublin"), TravelCard ("New York", "Habana")

Answer 1

除非您有大量卡片，否则您的解决方案将有效。否则，您可以考虑使用 2 个字典来使搜索保持不变并保持 O(N) 复杂度:

namespace ConsoleApplication
{
    public class Dominoe
    {
        public Dominoe(int left, int right)
        {
            LeftSide = left;
            RightSide = right;
        }

        public int LeftSide;
        public int RightSide;
    }

    class Program
    {
        static void Main(string[] args)
        {
            var input = new List<Dominoe>()
            {
                new Dominoe(2, 3), 
                new Dominoe(1, 2), 
                new Dominoe(4, 5), 
                new Dominoe(3, 4)
            };

            var dicLeft = new Dictionary<int, Dominoe>();
            var dicRigth = new Dictionary<int, Dominoe>();

            foreach (var item in input)
            {
                dicLeft.Add(item.LeftSide, item);
                dicRigth.Add(item.RightSide, item);
            }

            Dominoe first = null;

            foreach(var item in input)
            {
                if (!dicRigth.ContainsKey(item.LeftSide))
                {
                    first = item;
                    break;
                }
            }

            Console.WriteLine(string.Format("{0} - {1}", first.LeftSide, first.RightSide));

            for(int i = 0; i < input.Count - 1; i++)
            {
                first = dicLeft[first.RightSide];
                Console.WriteLine(string.Format("{0} - {1}", first.LeftSide, first.RightSide));
            }

            Console.ReadLine();
        }
    }
}