算法设计与分析第二周练习

目录更多技术博客 http://vilins.top/Kth Largest Element in an Array(分治算法)Course Schedule(拓扑)#Kth Largest Element in an Array#题目Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.##ExampleInput: [3,2,1,5,6,4] and k 2 Output: 5##ExampleInput: [3,2,3,1,2,4,5,5,6] and k 4 Output: 4##分析####分治算法的概念在计算机科学中分治法是建基于多项分支递归的一种很重要的算法范式。字面上的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题直到最后子问题可以简单的直接求解原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础如排序算法快速排序、归并排序、傅立叶变换快速傅立叶变换。这题有两个思路全部排序是不可能的第一个思路是建一个堆其大小为k-1这个堆是有序的当堆没满的时候将元素直接插入堆中当堆满后我们可以有取舍进行操作当遍历的元素小于堆的最小元素堆的第一个元素我们不需要处理当遍历的元素大于堆顶元素时pop堆顶元素将元素插入到堆中。最后堆顶的元素即为第k大的元素。第二个思路就是运用分治算法具体算法的过程:是找一个数组元素将数组中比这个元素大的元素放到这个元素的前面比这个元素小的元素放到这个元素的后面。如果这个元素的下标刚好等于k-1则返回如果下标大于k-1则在前面的元素用同样的办法找如果下标小于k-1则在后面的元素用同样的办法找。这样不断的把这个问题一分为二不断减少问题的规模而且问题的本质没有发生变化。这周刚好讲了分治算法我们就拿这个简单的求第k大的数来练练手由于数组是随机的所以算法的时间复杂度是有提高的以第一个例子为例具体的过程如下本来数组【321564】第一遍分治3作为标志的数结果为 【564321】。然后k2目标数在左边。第二遍分治处理的目标是【564】5作为标志数结果为【654】此时判断target5刚好下标是1也就是第二大的数。##源码class Solution { public: int findKthLargest(vectorint nums, int k) { int r nums.size() - 1, left 0, right r, l left; while(1) { l left 1; r right; //cout b tag l r endl; while(l r) { if(nums[l] nums[left]nums[r] nums[left]) { int temp nums[l]; nums[l] nums[r]; nums[r] temp; l; r--; } if(nums[r] nums[left]) { r--; } if(nums[l] nums[left]) { l; } } int temp nums[left]; nums[left] nums[r]; nums[r] temp; int result r; if((k result 1)) { return nums[result]; } else if(result k - 1) { left result 1; } else { right result - 1; } //cout 1 tag l r endl; } } };#Course Schedule(拓扑)##题目There are a total of n courses you have to take, labeled from 0 to n-1.Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?####ExampleInput: 2, [[1,0]] Output: true Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.####ExampleInput: 2, [[1,0],[0,1]] Output: false Explanation: There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.##分析这题是图论方面的题目在leetcode只有那么仅仅的几道题。同时这也是Topological Sort的代表性题目通过规定完成某个事件之前必须要完成某些特点的事件也就是事件之间有明确的先后顺序这些事件完成的顺序不一定只有一种但必须满足某些事件的特定的顺序这样所形成的序列被称为拓扑序列选课之前完成某些先导课程这样便是典型的例子。题目要求我们判断所给出的序列是否为拓扑序列根据拓扑序列的特征事件构成的图是无环的。我们得出一下判断的算法。图的每个点都对应着入度和出度在初始情况下只有那些起点的入度为0一个拓扑序列可以有多个起点所以我们将起点存放在一个队列中。先计算每个点的入度。从起点开始遍历遍历到入度就少1将入度为0的点push进栈中变为起点这是不再关注其入度当成起点处理。遍历完所有的起点最后如果某个点入度不为0那么就证明序列有环。##源码class Solution { public: bool canFinish(int numCourses, vectorpairint, int prerequisites) { vectorint in(numCourses,0); queueint empty; vectorvectorint temp(numCourses, vectorint(0)); //建立图vector的二维数组 for(auto a : prerequisites) { temp[a.second].push_back(a.first); in[a.first]; } //将入度为0的点存进队列里面 for(int i 0; i numCourses; i) { if(in[i] 0) { empty.push(i); } } //入度为0的点作为开始的点检查是否有环 while(!empty.empty()) { int frist_point empty.front(); empty.pop(); for(auto a : temp[frist_point]) { in[a]--; if(in[a] 0) { empty.push(a); } } } for(int i 0; i numCourses; i) { if(in[i] ! 0) { return false; } } return true; } };更多技术博客 http://vilins.top/