时间戳

首页 > 解决方案 > 与原点最近的 K 个点（K 个最小元素），hoare 的分区没有给出特定输入的正确答案

c# - 与原点最近的 K 个点（K 个最小元素），hoare 的分区没有给出特定输入的正确答案

问题描述

我正在解决这个问题：https ://leetcode.com/problems/k-closest-points-to-origin/

简而言之，给定一个点列表返回最接近原点的 K，其中 K 中的顺序无关紧要。我正在尝试使用 Hoare 分区的 quickselect 变体来解决这个问题，但是对于特定的输入，它没有给出正确的答案，我无法弄清楚为什么。Hoare 的分区逻辑本身是从 wikipedia 复制的。

点数：[[68,97],[34,-84],[60,100],[2,31],[-27,-38],[-73,-74],[-55,-39], [62,91],[62,92],[-57,-67]] K:5

namespace N
{
    using System;
    using System.Collections.Generic;
    using System.Linq;
    using System.Text;

    public class Solution
    {
        private readonly Random rand = new Random();
        public int[][] KClosest(int[][] points, int K)
        {
            var result = new List<int[]>();
            KClosestHelper(points, 0, points.Count() - 1, K);
            return points.Take(K).ToArray();
        }

        private void KClosestHelper(int[][] points,
                                        int left,
                                        int right,
                                        int k)
        {
            if (left >= right) return;

            var partitionIndex = Partition(points, left, right);
            int leftLength = partitionIndex - left + 1;
            if (k < leftLength)
            {
                KClosestHelper(points, left, partitionIndex - 1, k);
            }
            else if (k > leftLength)
            {
                KClosestHelper(points, partitionIndex + 1, right, k - leftLength);
            }
        }

        private int Partition(int[][] arr, int left, int right)
        {
            //var randomIndex = rand.Next(left, right+1);
            //swap(arr, left, randomIndex);
            var pivot = arr[left];
            left--;
            right++;

            while (true)
            {
                do
                {
                    left++;
                } while (AIsCloserThanB(arr[left], pivot));

                do
                {
                    right--;
                } while (AIsFartherThanB(arr[right], pivot));

                if (left >= right) return right;

                swap(arr, left, right);
            }
        }

        private bool AIsCloserThanB(int[] a, int[] b)
        {
            return a[0] * a[0] - b[0] * b[0] + a[1] * a[1] - b[1] * b[1] < 0;
        }

        private bool AIsFartherThanB(int[] a, int[] b)
        {
            return a[0] * a[0] - b[0] * b[0] + a[1] * a[1] - b[1] * b[1] > 0;
        }

        private void swap(int[][] arr, int i, int j)
        {
            var temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    public class MainClass
    {
        public static void Main()
        {
            var arr = new int[10][];
            arr[0] = new[] { 68, 97 };
            arr[1] = new[] { 34, -84 };
            arr[2] = new[] { 60, 100 };
            arr[3] = new[] { 2, 31 };
            arr[4] = new[] { -27, -38 };
            arr[5] = new[] { -73, -74 };
            arr[6] = new[] { -55, -39 };
            arr[7] = new[] { 62, 91 };
            arr[8] = new[] { 62, 92 };
            arr[9] = new[] { -57, -67 };
            var s = new Solution();
            var closest = s.KClosest(arr, 5);
            foreach (var item in closest)
            {
                Console.Out.WriteLine(string.Join(",", item));
            }
        }
    }

}

在使用 left ==3 和 right ==7 的 Partition 调用中进行调试时，首先交换 3 和 7（所以现在左边是 3，右边是 7）。然后left一直到7，并且由于do while right变成了6，它作为分区返回。但这是不正确的，因为 points[5] 是 [-73,74] 而 points[6] 是 [-57,67]（所以 points[5] > points[6]）。我认为 7 应该作为分区返回。这导致最终解决方案包含 [-73,-74] 而不是 [-57,67]。有人可以帮我理解算法的哪一部分不正确/不适用于这个问题，因为维基百科的逻辑必须是正确的？

标签： c#algorithmquicksort

解决方案

定义Point类

public class Point
{
    public int X;
    public int Y;
}

现在将您的观点放入Point[] points并执行简单的 linq 查询

var closest = points.OrderBy(p => p.X * p.X + p.Y * p.Y).Take(k);

如果您不需要完整排序的集合，最新版本的 .NET 足够智能，可以使用QuickSelect ，因此预期的复杂性应该是O(k log N)

推荐阅读