一个快速找第k+1小的算法
2024-09-12 21:00:32
public static int randomSelect(int[] A, int k)
{
return randomSelectDo(A, 0, A.Length - 1, k);
} private static int randomSelectDo(int[] A, int low, int high, int k)
{
int i = randomPartition(A, low, high);
//n is the number of < A[i]
int n = i - low;
if (n > k)
return randomSelectDo(A, low, i - 1, k);
else if (n == k)
return A[i];
else
return randomSelectDo(A, i + 1, high, k - n - 1);
} private static void swap(int[] A, int i, int j)
{
int temp = A[i];
A[i] = A[j];
A[j] = temp;
} private static int randomPartition(int[] A, int low, int high)
{
//random divide
Random rand = new Random();
int r = rand.Next(high - low + 1) + low;
swap(A, low, r);
int i = low;
int x = A[low];
for (int j = low + 1; j <= high; j++)
{
if (A[j] < x)
{
i++;
if (i != j)
{
swap(A, i, j);
}
}
}
swap(A, low, i);
return i;
}
static void Main(string[] args)
{
int[] I = new int[10];
Random r = new Random();
B:
for (int i = 0; i < I.Length; i++)
{
I[i] = r.Next(20);
} foreach (int i in I)
{
Console.Write(i+" ");
}
Console.WriteLine("_______________________________________"); int t= randomSelect(I, 0);
Console.WriteLine(t);
if (Console.ReadLine() == "a")
{
goto B;
}
}
最新文章
- 115个Java面试题和答案——终极列表（下）
- DirectoryInfo类
- Linux下统计出现次数最多的指定字段值
- POJ 3274 Gold Balanced Lineup 哈希,查重 难度:3
- 使用WIF实现单点登录Part II —— Windows Identity Foundation基本原理
- C/C++：类模板
- floor() 和 ceil()函数
- Handler处理长时间事件
- Xcode8插件安装
- uCOS-II
- 【PMP】易混淆知识点
- xdg-open命令智能打开各种格式的文件
- HttpClient的POST请求返回302解决
- 计算机&通信词典
- wordpress WP-PageNavi分页
- 通过微信Android和iOS版，看两大系统的差异
- c++浅拷贝与深拷贝(LeetCode669)
- linux 分卷压缩和合并
- pycharm控制台出现python编译器的编辑功能
- CodeChef SADPAIRS：Chef and Sad Pairs