# C#刷剑指Offer | 【常考题】最小的k个数

2020/11/10 14:13

【C#刷题作者 / Edison Zhou

1题目介绍

2解题思路与实现

But，采用这种思路是有限制的。我们需要修改输入的数组，因为函数Partition会调整数组中数字的顺序。

public static void GetLeastNumbersByRedBlackTree(List<int> data, SortedDictionary<int, int> leastNumbers, int k)
{
leastNumbers.Clear();

if (k < 1 || data.Count < k)
{
return;
}

for (int i = 0; i < data.Count; i++)
{
int num = data[i];
if (leastNumbers.Count < k)
{
}
else
{
int greastNum = leastNumbers.ElementAt(leastNumbers.Count - 1).Value;
if (num < greastNum)
{
leastNumbers.Remove(greastNum);
}
}
}
}


3单元测试

public static void TestPortal(string testName, int[] data, int[] expected, int k)
{
if (!string.IsNullOrEmpty(testName))
{
Console.WriteLine("{0} begins:", testName);
}

Console.WriteLine("Result for solution:");
if (expected != null)
{
Console.WriteLine("Expected result:");
for (int i = 0; i < expected.Length; i++)
{
Console.Write("{0}\t", expected[i]);
}
Console.WriteLine();
}

if(data == null)
{
return;
}

List<int> dataList = new List<int>();
for (int i = 0; i < data.Length; i++)
{
}
SortedDictionary<int, int> leastNumbers = new SortedDictionary<int, int>();
GetLeastNumbersByRedBlackTree(dataList, leastNumbers, k);
Console.WriteLine("Actual result:");
foreach (var item in leastNumbers)
{
Console.Write("{0}\t", item.Value);
}
Console.WriteLine("\n");
}



// k小于数组的长度
public static void Test1()
{
int[] data = { 4, 5, 1, 6, 2, 7, 3, 8 };
int[] expected = { 1, 2, 3, 4 };
TestPortal("Test1", data, expected, expected.Length);
}

// k等于数组的长度
public static void Test2()
{
int[] data = { 4, 5, 1, 6, 2, 7, 3, 8 };
int[] expected = { 1, 2, 3, 4, 5, 6, 7, 8 };
TestPortal("Test2", data, expected, expected.Length);
}

// k大于数组的长度
public static void Test3()
{
int[] data = { 4, 5, 1, 6, 2, 7, 3, 8 };
int[] expected = null;
TestPortal("Test3", data, expected, 10);
}

// k等于1
public static void Test4()
{
int[] data = { 4, 5, 1, 6, 2, 7, 3, 8 };
int[] expected = { 1 };
TestPortal("Test4", data, expected, expected.Length);
}

// k等于0
public static void Test5()
{
int[] data = { 4, 5, 1, 6, 2, 7, 3, 8 };
int[] expected = null;
TestPortal("Test5", data, expected, 0);
}

// 数组中有相同的数字
public static void Test6()
{
int[] data = { 4, 5, 1, 6, 2, 7, 2, 8 };
int[] expected = { 1, 2 };
TestPortal("Test6", data, expected, expected.Length);
}

// 输入空指针
public static void Test7()
{
TestPortal("Test7", null, null, 0);
}


4分布式计算

（1）map方法

public static class MyMapper extends
Mapper<LongWritable, Text, NullWritable, LongWritable> {
public static final int K = 100;
private TreeMap<Long, Long> tm = new TreeMap<Long, Long>();

protected void map(
LongWritable key,
Text value,
Mapper<LongWritable, Text, NullWritable, LongWritable>.Context context)
throws java.io.IOException, InterruptedException {
try {
long temp = Long.parseLong(value.toString().trim());
tm.put(temp, temp);
if (tm.size() > K) {
tm.remove(tm.firstKey());
// 如果是求topk个最小的那么使用下面的语句
//tm.remove(tm.lastKey());
}
} catch (Exception e) {
context.getCounter("TopK", "errorLog").increment(1L);
}
};

protected void cleanup(
throws java.io.IOException, InterruptedException {
for (Long num : tm.values()) {
context.write(NullWritable.get(), new LongWritable(num));
}
};
}


（2）reduce方法

public static class MyReducer extends
Reducer<NullWritable, LongWritable, NullWritable, LongWritable> {
public static final int K = 100;
private TreeMap<Long, Long> tm = new TreeMap<Long, Long>();

protected void reduce(
NullWritable key,
java.lang.Iterable<LongWritable> values,
Reducer<NullWritable, LongWritable, NullWritable, LongWritable>.Context context)
throws java.io.IOException, InterruptedException {
for (LongWritable num : values) {
tm.put(num.get(), num.get());
if (tm.size() > K) {
tm.remove(tm.firstKey());
// 如果是求topk个最小的那么使用下面的语句
//tm.remove(tm.lastKey());
}
}
// 按降序即从大到小排列Key集合
for (Long value : tm.descendingKeySet()) {
context.write(NullWritable.get(), new LongWritable(value));
}
};
}


（3）实现效果：图片大小有限，这里只显示了前12个；

Ref参考资料

????扫码关注EdisonTalk

0
0 收藏

0 评论
0 收藏
0