K ближайших точек к началу координат (K наименьших элементов) с разбиением Hoare, не дающим правильного ответа для конкретного ввода

Question

Я решаю этот вопрос: https://leetcode.com/problems/k-closest-points-to-origin/

Вкратце, учитывая список точек, верните K, ближайший к началу координат, где порядок в K не имеет значения. Я пытаюсь решить эту проблему с помощью варианта быстрого выбора с использованием разбиения Хоара, но для конкретного ввода это не дает правильного ответа, и я не могу понять, почему. Сама логика разбиения Hoare скопирована из википедии.

Баллы: [[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));
            }
        }
    }

}

При отладке в вызове раздела с левым == 3 и правым == 7, 3 и 7 меняются местами первыми (теперь слева 3 и справа 7). Затем left идет до 7, и из-за do while право становится 6, которое возвращается как раздел. Но это неверно, поскольку точки [5] равны [-73,74], а точки [6] - [-57,67] (поэтому точки [5]> точки [6]). Я думаю, что 7 должен был быть возвращен как раздел. Это приводит к окончательному решению, содержащему [-73, -74] вместо [-57,67]. Может кто-нибудь помочь мне понять, какая часть алгоритма неверна / неприменима к этой проблеме, так как логика википедии должна быть правильной?

Answer 1

не знаю, почему результат, но так как это c #, почему бы вам не упростить код. определить метод, возвращающий расстояние

private static double DistanceToCenter(int[] p)
    {
        return Math.Sqrt(p[0] ^ 2 + p[1] ^ 2);
    }

затем используйте linq:

var s = arr.OrderBy(p => DistanceToCenter(p));

это даст вам список, отсортированный по расстоянию до 0.0, затем сначала выберите k для распечатки.

Answer 2

Определить 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)