algorithm - 連鎖情報を持つペアデータのリストから一意の名前の数を見つける方法は?

Question

「n」行のデータ セットがあり、各データ セットにはスペースで区切られた 2 つのコンポーネントがあります。1つ目はカード番号、2つ目は名前です。カード番号や名前が同じ人は同じです。データセットからユニークな人の総数を見つける方法は?

例：

1A

1B

2B

3C

このデータ セットには 2 人の一意の人物が含まれています。これは、1 列目と 2 列目のカード番号が同じで、2 列目と 3 列目の名前が同じであるためです。

この種の問題を解決するには、どのようなアルゴリズムを使用できますか?

Answer 1

グラフ理論と連結成分を使用した別のソリューションを次に示します。

              int CountUnique(Person[] persons)
                Dictionary<string, int> phones = new Dictionary<string, int>();
                Dictionary<string, int> emails = new Dictionary<string, int>();
                bool[] unique = new bool[n];
                int count = 0;
                int max = 0;
                for (int i = 0; i < n; i++)
                {
                    Person p = persons[i];
                    int pA = -1, pB = -1;
                    if (phones.ContainsKey(p.Phone))
                    {
                        pA = phones[p.Phone];
                    }
                    if (emails.ContainsKey(p.Email))
                    {
                        pB = emails[p.Email];
                    }
                    if (pA != -1)
                    {
                        persons[pA].Next.Add(p);
                        p.Next.Add(persons[pA]);
                    }
                    else
                    {
                        phones.Add(p.Phone, p.Index);
                    }

                    if (pB != -1 && pB != pA)
                    {
                        persons[pB].Next.Add(p);
                        p.Next.Add(persons[pB]);
                    }
                    if (pB == -1)
                    {
                        emails.Add(p.Email, p.Index);
                    }
                }


                int current = 0;
                Person pCurrent;
                count = 0;
                while ((pCurrent = FindUnvisited(persons, current)) != null)
                {
                    BFS(pCurrent);
                    count++;
                }

                return count;


            }

            private static void DFS(Person pCurrent)
            {
                pCurrent.Visited = true;
                foreach (Person p in pCurrent.Next)
                {
                    if (!p.Visited)
                    {
                        BFS(p);
                    }
                }
            }

            private static Person FindUnvisited(Person[] persons, int current)
            {
                for (int i = current; i < persons.Length; i++)
                {
                    if (persons[i].Visited == false) return persons[i];
                }
                return null;
            }


        }
    }

Answer 2

C++の並べ替え。ただし、疑似コードと見なしてください。

int uniqueCount = 0;
map<string, bool> column_1;
map<string, bool> column_2;
string left, right
for(int x = 0 ;x < matrix.count; x++) {
   left = matrix[x][0]
   right = matrix[x][1];
   if(column_1.find(left) != column_1.end && column_2.find(right) != column_2.end){
  ++uniqueCount 
   column_1[left] = true;
   column_2[right] = true;
   }
  else --uniqueCount;
}

上記がコンパイルされていない場合は、申し訳ありません。疑似コードとして考えてみましょう。私はしばらく C++ を使用していなかったので、Rails コードが役立つとは思いませんでした。

Answer 3

私が思いついた解決策は、ある種のパーティショニングを使用することです。ほとんどの操作は O(1) または O(logn) で行われ、ユーザーによって一度行われるため、時間の複雑さは約 O(n),O(logn) になります。 Dictionary の実装方法によって異なります。

int CountUnique(Person persons)
{
        Dictionary<string, int> phones = new Dictionary<string, int>(); //Keep a dictionary where each phone number is mapped to a partition
        Dictionary<string, int> email = new Dictionary<string, int>();  //Keep a dictionary where each email is mapped to a partition
        bool[,] linked = new bool[n, n]; //Lookup table used to tell if 2 partitions are linked (represents the same person)
        int count = 0;
        int max = 0;
        for (int i = 0; i < n; i++)
        {
            Person p = persons[i];
            int pA = -1, pB = -1; // Partition found using the phone number, Partition found using email
            if (phones.ContainsKey(p.Phone))
            {
                pA = phones[p.Phone];
            }
            if (emails.ContainsKey(p.Email))
            {
                pB = emails[p.Email];
            }

            if (pA == -1 && pB == -1) // First case, not found: Add both phones and email and create a new partition. Number of unique persons is also incremented.
            {
                phones.Add(p.Phone.Trim(), max);
                emails.Add(p.Email.Trim().ToLower(), max);
                max++;
                count++;
            }
            else
            {
                if (pA != -1 && pB != -1 && pA != pB) // Found using both parameters on different partitions
                {
                    if (!linked[pA, pB] && !linked[pB, pA]) // If the partition are not linked, link them
                    {
                        count--; // We'lost one partition => one unique person less
                        linked[pA, pB] = linked[pB, pA] = true;
                    }
                }
                if (pA == -1) // We did find an existing email but no phone
                {
                    phones.Add(p.Phone.Trim(), pB); // Add the phone number
                    max++;
                }
                if (pB == -1) // We did find an existing phone but no email
                {
                    emails.Add(p.Email.Trim().ToLower(), pA); // Add the email number
                    max++;
                }
            }

        }



return count;
}