Algorithm Design and Analysis Week 2 Practice

目录

Course Schedule (Topology) Kth Largest Element in an Array

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.

Example

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

分析

This week just talked about the divide and conquer algorithm, we will take this simple to ask for the k-th number to practice. In fact, this problem can also be done by stack method, but we still need to be familiar with the divide and conquer algorithm. Since the array is random, the time complexity of the algorithm is improved. The process of the specific algorithm:

  • is to find an array element, put the element in the array larger than this element in front of this element, than this The small element of the element is placed after this element.
  • If the subscript of this element is exactly equal to k-1, then return; if the subscript is greater than k-1, then the previous element is found in the same way; if the subscript is less than k-1, then in the latter The elements are found in the same way.

This continually divides this problem into two, constantly reducing the scale of the problem, and the nature of the problem has not changed. Taking the first example as an example, the specific process is as follows: 3 as the number of signs, 5, 6, 4, 3, 2, 1 Then k=2, the target number is on the left 5 as the number of signs, 6, 5, 4 This is the answer.

来源

class Solution {
public:
    int findKthLargest(vector<int>& 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(Topology)

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?

Example

Input: 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.

Example

Input: 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.

分析

This question is a graph theory topic, only a few questions in leetcode. At the same time, this is also a representative topic of Topological Sort. It is necessary to complete certain events before completing an event, that is, there is a clear sequence between events. The order of completion of these events is not necessarily one, but it must be The specific order of certain events is met, and the resulting sequence is called a topological sequence. This is a typical example of completing some lead courses before class selection. The question asks us to judge whether the given sequence is a topological sequence. According to the characteristics of the topological sequence: the graph of the event is acyclic. We come up with an algorithm for judging. Each point of the

  • graph corresponds to the degree of ingress and out. In the initial case, only those starting points have an indegree of 0, and a topological sequence can have multiple starting points.
  • First calculate the indegree of each point.
  • traverses from the starting point, traversing to the degree of entry is less than 1, pushing the point with the degree of zero into the stack.
  • Finally, if a point-in degree is not 0, then the sequence is proved to have a ring.

来源

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<int> in(numCourses,0);
        queue<int> empty;
        vector<vector<int> > temp(numCourses, vector<int>(0));
        //Create a map, a two-dimensional array of vectors 
        for(auto a : prerequisites) {
            temp[a.second].push_back(a.first);
            in[a.first]++;
        }

        //Save the point with a degree of 0 into the queue 
        for(int i = 0; i < numCourses; i++) {
            if(in[i] == 0) {
                empty.push(i);
            } 
        }
        // The point with a degree of 0 is started Point, check if there is a ring
        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;
    }
};