【C# 每日一题3】求第K大的数
原题如下：DescriptionThere are two sequences A and B with N (1<=N<=10000) elements each. All of the elements are positive integers. Given C=A*B, where '*' representing Cartesian product, c = a*b, where c belonging to C, a belonging to A and b belonging to B. Your job is to find the K'th largest element in C, where K begins with 1.InputInput file contains multiple test cases. The first line is the number of test cases. There are three lines in each test case. The first line of each case contains two integers N and K, then the second line represents elements in A and the following line represents elements in B. All integers are positive and no more than 10000. K may be more than 10000.OutputFor each case output the K'th largest number.Sample Input22 13 45 62 32 14 8Sample Output248
using System;namespace CSharpTest{ class Program { public static int[] A = new int[1000000], B = new int[1000000]; public static Random Rnd = new Random(2010);//统一一个随机种子好验证 public static void FillRandomValues(int[] arr)//随机填充 { for (var i = 0; i < arr.Length; i++) arr[i] = Rnd.Next(); } public static void Main() { FillRandomValues(A); FillRandomValues(B); //排序 Array.Sort<int>(A); Array.Sort<int>(B); //根据输入的K输出结果 while (true) { long k; if (long.TryParse(Console.ReadLine(), out k)) { if (k == 0) break; Console.WriteLine(KthElement(k)); } } } //求第K个元素 static long KthElement(long k) { //该数肯定位于upper和lower之间 long upper = (long)A[A.Length - 1] * B[B.Length - 1], lower = A[0] * B[0]; return Solve(upper, lower, k); } //二分查找该值 static long Solve(long upper, long lower, long count) { if (upper == lower) return upper; long mid = (upper + lower) >> 1; if (Counter(mid) >= count) return Solve(upper, mid + 1, count); if (Counter(mid - 1) < count) return Solve(mid - 1, lower, count); return mid; } //统计比指定value大的数有多少个 static long Counter(long value) { int i = 0, j = B.Length - 1; long count = 0; while (i < A.Length && j >= 0) { if ((long)A[i] * (long)B[j] > value) { count += A.Length - i; j--; } else i++; } return count; } }}
[解决办法]
用堆排序求第K大数据比较好
------解决方案--------------------
来学习。
[解决办法]
来学习
[解决办法]
Sample Input
[解决办法]
namespace FindN{ public class Comparer : IComparer<int> { public int Compare(int x, int y) { return x.CompareTo(y) * -1; } } class Program { static void Main(string[] args) { List<int> a = new List<int>(); List<int> b = new List<int>(); a.Add(2); a.Add(3); a.Add(7); //a.Add(9); b.Add(4); b.Add(8); b.Add(5); Comparer c = new Comparer(); a.Sort(c); b.Sort(c); int v =Program.Find(a, b, 3); } static int Find(List<int> a, List<int> b, int n) { int ac = a.Count; int bc = b.Count; int av = a[0]; int bv = b[0]; int c = 0; for (int i = 1; i < a.Count;) { for (int j = 1; j < b.Count; ) { if (b[j] > a[i]) { if (c + ac > n) { return a[n - c] * b[j]; } c += ac; bv = b[j]; j++; } else { if (c + bc > n) { return a[i] * b[n - c]; } c += bc; av = a[i]; i++; } } } throw new Exception(); } }}
[解决办法]
前K大的问题，一定是O(n)的，30年前早有定论。
看算法导论和TAOCP
[解决办法]
学习了
[解决办法]
嘿嘿，笨狼兄还是仔细看看此题吧，哪有这么简单？
[解决办法]
学习了，看到算法题就头痛，。
[解决办法]
不知道啊.以后再看看书,再来回答各位了.
[解决办法]
希望以后会懂得更多啊
[解决办法]
ertgwygwyweywert