Python程式：將一組點分成k個不同組

假設我們有一組點和一個數字k。這些點以(x, y)的形式表示笛卡爾座標。如果任意兩點p1和p2之間的歐幾里德距離<=k，我們可以將它們分組，我們需要找到不相交組的總數。

因此，如果輸入類似於 points = [[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]]，k = 2，則輸出將為2，因為它可以構成兩個組：([2,2],[3,3],[4,4])和([11,11],[12,12])

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式dfs()。它將接收i作為引數。

  • 如果i在seen中，則

    • 返回

    • 將i插入seen

    • 對adj[i]中的每個nb，執行：

      • dfs(nb)

      • 在主方法中，執行以下操作：

      • adj := 一個對映

      • n := points的大小

      • 對於範圍0到n內的j，執行：

        • 對於範圍0到j內的i，執行：

          • p1 := points[i]

          • p2 := points[j]

          • 如果p1和p2之間的歐幾里德距離<k，則

            • 將j插入adj[i]的末尾

            • 將i插入adj[j]的末尾

      • seen := 一個新的集合

      • ans := 0

      • 對於範圍0到n內的i，執行：

        • 如果i不在seen中，則

          • ans := ans + 1

          • dfs(i)

      • 返回ans

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

from collections import defaultdict
class Solution:
   def solve(self, points, k):
      adj = defaultdict(list)

      n = len(points)
      for j in range(n):
         for i in range(j):
            x1, y1 = points[i]
            x2, y2 = points[j]
            if (x1 - x2) ** 2 + (y1 - y2) ** 2 <= k ** 2:
               adj[i].append(j)
               adj[j].append(i)

      seen = set()
      def dfs(i):
         if i in seen:
            return
         seen.add(i)
         for nb in adj[i]:
            dfs(nb)

      ans = 0
      for i in range(n):
         if i not in seen:
            ans += 1
            dfs(i)
      return ans
ob = Solution()
points = [
[2, 2],
[3, 3],
[4, 4],
[11, 11],
[12, 12]
]
k = 2
print(ob.solve(points, k))

輸入

[[2, 2],[3, 3],[4, 4],[11, 11],[12, 12]],2

輸出

2

更新於：2020年10月8日

瀏覽量：597

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告