shamsminoo
BAN USERusing System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
class Solution {
static void Main(String[] args)
{
Point[] arr = { new Point(1, 1), new Point(4, 4), new Point(5, 5), new Point(3, 3), new Point(2, 2), new Point(6, 6), new Point(9, 9),
new Point(15, 15), new Point(11, 11), new Point(10, 10), new Point(13, 13), new Point(12, 12), new Point(14, 14), new Point(7, 7),};
for (int i = 0; i < arr.Length; i++)
{
Console.Write("(" + arr[i].X + ", " + arr[i].Y + "), ");
}
Console.WriteLine();
QuickSelectK( arr, 0, arr.Length,2);
for (int i = 0; i < arr.Length; i++)
{
Console.Write("(" + arr[i].X + ", " + arr[i].Y + "), ");
}
Console.WriteLine();
Console.In.ReadLine();
}
public struct Point {
public Point(int x, int y)
{
this.x = x;
this.y = y;
}
private int x;
private int y;
public int X { get { return x; } set{ x= value; }}
public int Y { get { return y; } set { y = value; }}
public static bool operator <(Point p1, Point p2)
{
return (p1.X * p1.X + p1.Y * p1.Y) < (p2.X * p2.X + p2.Y * p2.Y);
}
public static bool operator >(Point p1, Point p2)
{
return (p1.X * p1.X + p1.Y * p1.Y) > (p2.X * p2.X + p2.Y * p2.Y);
}
}
public static int QuickSelectionPartition(Point[] list, int left, int right, int pivotIndex)
{
Point pivotValue = list[pivotIndex];
//move pivot to right
list[pivotIndex] = list[right-1];
list[right-1] = pivotValue;
int storeIndex = left;
for(int i=left; i<right-1; i++)
{
if(list[i]<pivotValue)
{
Point temp = list[i];
list[i] = list[storeIndex];
list[storeIndex] = temp;
storeIndex++;
}
}
Point tempo = list[right-1];
list[right-1] = list[storeIndex];
list[storeIndex] = tempo;
return storeIndex;
}
public static void QuickSelectK(Point[]list, int left, int right, int k)
{
if (left == right) return;
int pivotIndex = (left + right) / 2;
pivotIndex = QuickSelectionPartition(list, left, right, pivotIndex);
if (pivotIndex == k)
return ;
else if (k < pivotIndex)
QuickSelectK(list, left, pivotIndex - 1, k);
else
QuickSelectK(list, pivotIndex + 1, right, k);
}
}
this code is in C# and according to Quickselect algorithm suggested in en.wikipedia.org//wiki//Quickselect
- shamsminoo March 31, 2017
Hi. I enhanced @parikksit.b solution for repeated keys and for cases where there are more than one match
- shamsminoo April 01, 2017