湖北专业网站建设耗材,营销策划名词解释,一个网站多个域名备案吗,手机网站建设制作教程视频【C#刷题】| 作者 / Edison Zhou这是EdisonTalk的第299篇学习分享我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目#xff08;精选了其中30道题目#xff09;#xff0c;希望对你有帮助#xff01;本文题目为#xff1a;最小的k个数。1题目介绍题目#… 【C#刷题】| 作者 / Edison Zhou这是EdisonTalk的第299篇学习分享我们来用之前学到的数据结构知识来刷《剑指Offer》的一些核心题目精选了其中30道题目希望对你有帮助本文题目为最小的k个数。1题目介绍题目输入n个整数找出其中最小的k个数。例如输入4、5、1、6、2、7、3、8这8个数字则最小的4个数字是1、2、3、4。这道题是典型的TopK问题其最简单的思路莫过于把输入的n个整数排序排序之后位于最前面的k个数就是最小的k个数。这种思路的时间复杂度是O(nlogn)但是面试官会要求时间复杂度保持在O(n)。2解题思路与实现思路1需要修改数据源的O(n)解法基于快速排序中的Partition函数来解决这个问题。如果基于数组的第k个数字来调整使得比第k个数字小的所有数字都位于数组的左边比第k个数字大的所有数字都位于数组的右边。这样调整之后位于数组中左边的k个数字就是最小的k个数字这k个数字不一定是排序的。But采用这种思路是有限制的。我们需要修改输入的数组因为函数Partition会调整数组中数字的顺序。思路2适合处理海量数据的O(nlogk)解法可以先创建一个大小为k的数据容器来存储最小的k个数字接下来我们每次从输入的n个整数中读入一个数。如果容器中已有的数字少于k个则直接把这次读入的整数放入容器之中如果容器中已有k个数字了也就是容器已满此时我们不能再插入新的数字而只能替换已有的数字。找出这已有的k个数中的最大值然后拿这次待插入的整数和最大值进行比较。如果待插入的值比当前已有的最大值小则用这个数替换当前已有的最大值如果待插入的值比当前已有的最大值还要大那么这个数不可能是最小的k个整数之一于是我们可以抛弃这个整数。因此当容器满了之后我们要做3件事情一是在k个整数中找到最大数二是有可能在这个容器中删除最大数三是有可能要插入一个新的数字。如果用一个二叉树来实现这个数据容器那么我们能在O(logk)时间内实现这三步操作。因此对于n个输入数字而言总的时间效率就是O(nlogk)。具体代码实现根据以上步骤这里采用C#实现代码如下采用了红黑树结构作为容器当然也可以采用堆来实现有关红黑树的细节可以阅读yangecnu的《浅谈算法和数据结构之红黑树》public static void GetLeastNumbersByRedBlackTree(Listint data, SortedDictionaryint, 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){leastNumbers.Add(num, num);}else{int greastNum leastNumbers.ElementAt(leastNumbers.Count - 1).Value;if (num greastNum){leastNumbers.Remove(greastNum);leastNumbers.Add(num, num);}}}
}
此解法虽然要慢一点但它有两个明显的优点一是没有修改输入的数据代码中的变量data。我们每次只是从data中读入数字所有的写操作都是在容器leastNumbers中进行的。二是该算法适合海量数据的输入包括百度在内的多家公司非常喜欢与海量输入数据相关的问题。假设题目是要求从海量的数据中找出最小的k个数字由于内存的大小是有限的有可能不能把这些海量的数据一次性全部载入内存。这个时候我们可以从辅助存储空间比如硬盘中每次读入一个数字根据GetLeastNumbers的方式判断是不是需要放入容器leastNumbers即可。这种思路只要求内存能够容纳leastNumbers即可因此它最适合的情形就是n很大并且k较小的问题。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;}Listint dataList new Listint();for (int i 0; i data.Length; i){dataList.Add(data[i]);}SortedDictionaryint, int leastNumbers new SortedDictionaryint, 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分布式计算Hadoop MapReduce简介Hadoop MapReduce是一个软件框架基于该框架能够容易地编写应用程序这些应用程序能够运行在由上千个商用机器组成的大集群上并以一种可靠的具有容错能力的方式并行地处理上TB级别的海量数据集。因此对于MapReduce可以简洁地认为它是一个软件框架海量数据是它的“菜”它在大规模集群上以一种可靠且容错的方式并行地“烹饪这道菜”。使用MapReduce解决TopK问题这里我们使用一个随机生成的100万个数字的文件也就是说我们要做的就是在100万个数中找到最大的前100个数字。实验数据下载地址http://pan.baidu.com/s/1qWt4WaS1map方法public static class MyMapper extendsMapperLongWritable, Text, NullWritable, LongWritable {public static final int K 100;private TreeMapLong, Long tm new TreeMapLong, Long();protected void map(LongWritable key,Text value,MapperLongWritable, 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(org.apache.hadoop.mapreduce.MapperLongWritable, Text, NullWritable, LongWritable.Context context)throws java.io.IOException, InterruptedException {for (Long num : tm.values()) {context.write(NullWritable.get(), new LongWritable(num));}};
}
其中这里使用到了java中的红黑树对应的数据结构TreeMap类cleanup()方法是在map方法结束之后才会执行的方法这里我们将在该map任务中的前100个数据传入reduce任务中2reduce方法public static class MyReducer extendsReducerNullWritable, LongWritable, NullWritable, LongWritable {public static final int K 100;private TreeMapLong, Long tm new TreeMapLong, Long();protected void reduce(NullWritable key,java.lang.IterableLongWritable values,ReducerNullWritable, 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));}};
}
在reduce方法中依次将map方法中传入的数据放入TreeMap中并依靠红黑色的平衡特性来维持数据的有序性。3实现效果图片大小有限这里只显示了前12个虽然例子很简单业务也很简单但是我们引入了分布式计算的思想将MapReduce应用在了最值问题之中也算是一个进步了。Ref参考资料何海涛《剑指Offer》后台回复剑指offer即可获得pdf下载链接哟????扫码关注EdisonTalk设为星标不再失联往期推文合集2020年上半年推文合集
