NO CODING NO LIFE: LeetCode

显示标签为“LeetCode”的博文。显示所有博文

2015年7月10日星期五

LeetCode: Course Schedule

As the hints, this problem is to find if a cycle exists in a directed graph.
Solution: Topological sort via DFS and BFS

Topological sort via DFS:

The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since the beginning of the topological sort or the node has no outgoing edges (i.e. a leaf node): (from WIKI)
Specifically, when the algorithm adds node n, we are guaranteed that all nodes which depend on n are already in the output list L:

L ← Empty list that will contain the sorted nodes
while there are unmarked nodes do
    select an unmarked node n
    visit(n) 
function visit(node n)
    if n has a temporary mark then stop (not a DAG)
    if n is not marked (i.e. has not been visited yet) then
        mark n temporarily
        for each node m with an edge from n to m do
            visit(m)
        mark n permanently
        unmark n temporarily
        add n to head of L

Initial ugly code with slow speed...

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        unordered_set<int> sortedList; 
        unordered_set<int> tempList;
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, prerequisites, sortedList, tempList)) return false;
        }
        return true;
    }
    bool visit(int n, vector<pair<int, int>>& prerequisites, unordered_set<int>& sortedList, unordered_set<int>& tempList){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(int i=0; i<prerequisites.size(); i++){
            if(prerequisites[i].first == n) {
                if( !visit(prerequisites[i].second, prerequisites, sortedList, tempList) ) return false;
            }
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

After putting sortedList and tempList in Line 4 and 5 above as a member of Solution, speed increases, but still not a good one.

class Solution {
public:
    unordered_set<int> sortedList; 
    unordered_set<int> tempList;
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        //unordered_set<int> sortedList; 
        //unordered_set<int> tempList;
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, prerequisites)) return false;
        }
        return true;
    }
    bool visit(int n, vector<pair<int, int>>& prerequisites){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(int i=0; i<prerequisites.size(); i++){
            if(prerequisites[i].first == n) {
                if( !visit(prerequisites[i].second, prerequisites) ) return false;
            }
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

Analysis:
This method visit each vertices, and visit() cost O(E)(Line 18) to visit adjacent nodes.
So the whole time complexity is O(v*E)
Defects: took too much time to search adjacent node.
How to overcome: Change graph representation from edge lists to adjacency matrices or adjacency lists. It will take O(E) to establish the new lists and O(v) for all node to look for adjacent nodes.
Then time complexity is O(E)+O(V)

Optimized codes:

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector< set<int> > adjLists(numCourses);
        unordered_set<int> sortedList; 
        unordered_set<int> tempList;
        //establish adjLists
        for(int i=0; i<prerequisites.size(); i++){
            adjLists[prerequisites[i].first].insert(prerequisites[i].second);
        }
        //traverse vertices
        for(int i=0; i<numCourses; i++){
            if(!sortedList.count(i)) 
               if(!visit(i, adjLists, sortedList, tempList)) return false;
        }
        return true;
    }
    bool visit(int n, vector<set<int>>& adjLists, unordered_set<int>& sortedList, unordered_set<int>& tempList){
        if(tempList.count(n)) return false;
        if(sortedList.count(n)) return true;
        tempList.insert(n);
        for(auto it=adjLists[n].begin(); it != adjLists[n].end(); ++it){
            if(!visit(*it, adjLists, sortedList, tempList)) return false;
        }
        sortedList.insert(n);
        tempList.erase(n);
        return true;
    }
};

Topological sort via BFS:
First, find a list of "start nodes" which have no incoming edges and insert them into a set S; at least one such node must exist in a non-empty acyclic graph. Then:

L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
    remove a node n from S
    add n to tail of L
    for each node m with an edge e from n to m do
        remove edge e from the graph
        if m has no other incoming edges then
            insert m into S
if graph has edges then
    return error (graph has at least one cycle)
else 
    return L (a topologically sorted order)

I use two sets to store edges.
IOLists stores all adjacent nodes that comes out from current index of vector
---- used to look for adjacent nodes for nodes in zeroInLists. (Line 19)
OILists stores all adjacent nodes that will come to the current index of vector
---- used to check the current node has no other incoming edges. (Line 23)

A normal BFS solution is to use array to record in-degree. Try later.

Note: 1. write sudo code before coding
2. give a good name, IOlist will be better than IOList, which adds many mistakes

class Solution {
public:
    bool canFinish(int numCourses, vector<pair<int, int>>& prerequisites) {
        vector<set<int>> IOLists(numCourses);
        vector<set<int>> OILists(numCourses);
        for(int i=0; i<prerequisites.size(); i++){
            IOLists[prerequisites[i].first].insert(prerequisites[i].second);
            OILists[prerequisites[i].second].insert(prerequisites[i].first);
        }
        queue<int> zeroInLists;
        for(int i=0; i<OILists.size(); i++){
            if(OILists[i].empty()) zeroInLists.push(i);
        }
        while(!zeroInLists.empty()){
            //remove one element
            int cur=zeroInLists.front();
            zeroInLists.pop();
            //get all adjacent nodes
            for(set<int>::iterator it=IOLists[cur].begin(); it!=IOLists[cur].end();++it){
            //for each node, remove the edge
                OILists[*it].erase(cur);
                //if this node don't have input, add to zeroInlists
                if(OILists[*it].empty()) zeroInLists.push(*it);
            }
            IOLists[cur].clear();
        }
        //if both IOLists and OILists are empty return true, else false
        for(int i=0; i<numCourses; i++){
            if(!IOLists[i].empty() || !OILists[i].empty()) return false;
        }
        return true;
    }
};

Reference:
About graph concepts:
in-degree, out-degree
graph representation

About this problem:
use the second sudo code for dfs
https://en.wikipedia.org/wiki/Topological_sorting#Algorithms
Use Yu's code to optimize:
http://yucoding.blogspot.com/2015/06/leetcode-question-course-schedule.html
Great explanation
http://www.cnblogs.com/grandyang/p/4484571.html

2015年7月6日星期一

LeetCode: Min Stack

There are two ways to record min:
1. with a stack. When pop an element in data, just check the last element in min stack. O(1);
2. with a variable. When pop an element in data, need to reiterate elements in data to get the min value. O(n)

class MinStack {
public:
    vector<int> data;
    vector<int> min;
    void push(int x) {
        data.push_back(x);
        /*
        if(min.empty()) {
            min.push_back(x);
            return;
        }
        if(x<=min.back()) min.push_back(x);*/
        //optimize
        if(min.empty() || min.back()>=x) 
            min.push_back(x);
    }
    void pop() {
        if(data.back() == min.back()) min.pop_back();
        data.pop_back();
    }
    int top() {
        return data.back();
    }

    int getMin() {
        return min.back();
    }
};

Here is a trick: stack just stores the difference of current element to previous minimum element. set a variable to store the minimum vanlue. Then we can realize O(1) to get minimum value with just one variable

push():
we need to get the minimum value before x is added
this is in two cases:
when the data is empty, minimum=input
when data is not empty, min now is the minimum value before the current back() element. So we need to compare min and the current back() element to get the min including back() value.

pop():
when pop the last element, for the previous element, the min may change, so we need to update the min value to pmin.
only when(p<pmin) min=p;
otherwise min=pmin.

Now p=pmin+pd(the data stored for p in stack);
p<pmin ==> pmin+pd<pmin ==> pd<0;
min=p ==> min=pmin+pd ==> pmin=min-pd

SO the condition becomes:
only when(pd<0) pmin=min-pd
otherwise pmin=min.

Then it's easy to update min to pmin.

Draw will help.
---------------------min--------
-------pmin---- |
| |
| |
xx x | p | last element in stack

class MinStack {
public:
    vector<int> data;
    int min;
    void push(int x) {
        //get the minimum value before x is added
        if(data.empty()) {
            min=x;
        }
        else{
            int prev=data.back()+min; //prev is the last value stored
            if(prev < min) min=prev;
        }
        data.push_back(x-min);
    }
    void pop() {
        data.pop_back();
        if(data.back()<0) min=min-data.back();
    }
    int top() {
        return data.back()+min;
    }
    int getMin() {
        return (top()<min)?top():min;
    }
};

Reference:
http://yucoding.blogspot.com/2014/12/leetcode-question-min-stack.html
http://blog.csdn.net/u010367506/article/details/41045797 //explain the trick way

2015年7月5日星期日

LeetCode: Power of Two

Node: in Line 6, the type of m should be double or run time error when input is more than 65537(2^16 + 1). Because when m=65536, m*m is out of range of Integer.

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n==0) return false;
        if(n==1) return true;
        double m=2;
        while(m*m<n){
            m=m*m;
        }
        if(n%(int)m != 0) return false;
        return isPowerOfTwo(n/m);
    }
};

LeetCode: Summary Ranges

In for loop, consider 2 cases:
1. consecutive to the previous, continue the loop
2. not consecutive to the previous, put string to the result, and i-- to reiterate the current element

I use an Integer length to mark how many numbers the string already has.
At the beginning, I use start and end index. But it makes the logics more complex.

Note: In for loop(line 7), only add s to result when checking the previous element is not continuous with the current one(Line 14). But for the last element of the array, no next element exists to do this judgement. So we have to add a judgement out of for loop.

class Solution {
public:
    vector<string> summaryRanges(vector<int>& nums) {
        vector<string> result;
        int length=0;
        string s;
        for(int i=0; i<nums.size(); i++){
            if(length == 0) {
                s.append(to_string(nums[i]));
                length++;
                continue;
            }
            //when consecutive
            if(nums[i]-nums[i-1] == 1){
                length++;
                continue;
            }
            //when not consecutive
            if(length >1){
                s.append("->");
                s.append(to_string(nums[i-1]));
            }
            result.push_back(s);
            s.clear();
            length=0;
            i--;
        }
        if(length==1) result.push_back(s);  //when one single range at the end of vector nums
        if(length > 1) {
            s.append("->");
            s.append(to_string(nums.back()));
            result.push_back(s);
        }
        return result;   
    }
};

Ugly codes. Need to optimize in the future.

Reference: http://blog.csdn.net/xudli/article/details/46645087

2015年7月4日星期六

LeetCode: Valid Palindrome

Initial solution:
Toooooo slow, almost same like python...

O(n)

class Solution {
public:
    bool isPalindrome(string s) {
        int size=s.size();
        for(int i=0; i<s.size(); i++){
            if(s[i] >= 'a' && s[i] <= 'z') continue;
            if(s[i] >= 'A' && s[i] <= 'Z'){
                s[i]=s[i]+'a'-'A';
                continue;
            }
            if(s[i] >= '0' && s[i] <= '9') continue;
            s.erase(i--, 1);
        }
        int length = s.size();
        for(int i=0; i < s.size()/2; i++){
            if(s[i] != s[length-1-i]) return false;
        }
        return true;
    }
};

Solution two,

Processing the string format and comparing char from left and right side of the string at the same time.
Codes are a little complex, but speed up a lot.

O(n)

class Solution {
public:
    bool validate(char c){
        if(c >='a' && c <= 'z') return true;
        if(c >='A' && c <= 'Z') return true;
        if(c >='0' && c <= '9') return true;
        return false;
    }
    bool isPalindrome(string s) {
        int left=0;
        int right=s.size()-1;
        while(left<right){
            while(!validate(s[left]) ) {
                left++;
                if(left >= right) break;
            }
            while(!validate(s[right])) {
                right--;
                if(right <= left) break;
            }
            if(left>=right) break;
            if(s[left] >= 'A'  && s[left] <='Z') s[left]=s[left]+'a'-'A';
            if(s[right] >= 'A'  && s[right] <='Z') s[right]=s[right]+'a'-'A';
            if(s[left] != s[right]) return false;
            left++;
            right--;
        }
        return true;
    }
};

Solution three:
Modify solution two in two ways:
1. change the ugly while loop to if ... continue;
2. add two library function to simplify codes.
#include<cctype> tolower() isalnum()

class Solution {
public:
    bool isPalindrome(string s) {
        int left=0;
        int right=s.size()-1;
        while(left<right){
            if(!isalnum(s[left]) ) {
                left++;
                continue;
            }
            if(!isalnum(s[right])) {
                right--;
                continue;
            }
            if(tolower(s[left]) != tolower(s[right])) return false;
            left++;
            right--;
        }
        return true;
    }
};

Reference: http://yucoding.blogspot.com/2013/05/leetcode-question-126-valid-palindrome.html

LeetCode: Pascal's Triangle II

Totally like Pascal's Triangle problem, just change the return.
n is the number of rows
Time: O(n*n) Space: O(n*n)

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<vector<int>> result(rowIndex+1);
        vector<int> row;
        for(int i=0; i<rowIndex+1; i++) {
            vector<int> row;
            for(int j=0; j<i+1; j++){
                if(j==0 || j==i) {
                    row.push_back(1);
                    continue;
                }
                row.push_back(result[i-1][j-1]+result[i-1][j]);
            }
            result[i]=row;
        }
        return result.back(); //when no element exist, the program will keep running, 
    }
};

Optimization:
To minimize the space complexity to O(2*n), use a vector to store the row above the current row.

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row_pre;
        for(int i=0; i < rowIndex+1; i++) {
            vector<int> row;
            for(int j=0; j < i+1; j++){
                if(j==0 || j==i) {
                    row.push_back(1);
                    continue;
                }
                row.push_back(row_pre[j-1]+row_pre[j]);
            }
            row_pre=row;
        }
        return row_pre; 
    }
};

Optimization 2:
With just one vector. Note the for loop condition.

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        vector<int> row;
        for(int i=0; i < rowIndex+1; i++) {
            for(int j=i-1; j >0 ; j--){  // NOTE: only add (i-1) times
                row[j]=row[j-1]+row[j];
            }
            row.push_back(1);
        }
        return row; 
    }
};

Optimization 3:
With math formula. No interest.

reference:
http://fisherlei.blogspot.com/2012/12/leetcode-pascals-triangle-ii.html
http://yucoding.blogspot.com/2013/04/leetcode-question-65-pascals-triangle-ii.html

LeetCode: Pascal's Triangle

0 1
1 1 1
2 1 2 1
3 1 3 3 1

Get each line from previous line. And set the beginning and ending to be 1.

Note the number of elements in each row is one bigger than the row index. So notice condition at Line7

O(n^2)

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> result;
        for(int i=0; i<numRows; i++){
            vector<int> row;
            for(int j=0; j<=i;j++){ //NOTE: <=i or <i+1
                if(j==0 || j==i) {
                    row.push_back(1); 
                    continue;
                }
                row.push_back(result[i-1][j-1]+result[i-1][j]);
            }
            result.push_back(row);
        }
        return result;
    }
};

LeetCode: Path Sum

The key is to understand the definition of leaf node: both kids are null, not just one.

From wiki:
An internal node (also known as an inner node, inode for short, or branch node) is any node of a tree that has child nodes. Similarly, an external node (also known as an outer node, leaf node, or terminal node) is any node that does not have child nodes.

Use recursion to check every path of the tree: O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL) return false;
        return getSum(root, 0, sum);
    }
    bool getSum(TreeNode* node, int pathsum, int sum ){
        if(node == NULL) {
            return false;
        }
        pathsum+=node->val;
        if(node->left == NULL && node->right == NULL) {
            if(pathsum == sum) return true;
            return false;
        }
        return (getSum(node->left, pathsum, sum) || getSum(node->right, pathsum, sum));
    }
};

If we keep reducing the sum by the traversed node value, then just one function is enough.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL) return false;
        if(root->left == NULL && root->right == NULL) {
            if(root->val == sum) return true;
            return false;
        }
        return hasPathSum(root->left, sum-root->val) || hasPathSum(root->right, sum-root->val);
    }
};

LeetCode: Balanced Binary Tree

First time bug free pass directly, cheers!

Divide and conquer method:
Here uses divide and conquer method for two function.
First is balance judgement.
O(n*n) (n=number of nodes)
For each element, calculate the left and right depth. If the distance of left and right depth is more than 1, return false. If not, test the left and right element.

Second is depth calculation.
O(n)
Get the longest depth of the current node.

Initial code:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int left, right;
        left = Caldeep(root->left);
        right = Caldeep(root->right);
        if(left - right >1 || right - left >1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
        
    }
    int Caldeep(TreeNode* node){
        if(node == NULL) return 0;
        int left=1, right=1;
        if(node->left != NULL) left = Caldeep(node->left)+1;
        if(node->right != NULL) right = Caldeep(node->right)+1;
        return (left>right)?left:right;
    }
};

Modified in a better format:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int left = Caldepth(root->left);
        int right = Caldepth(root->right);
        if(left-right >1 || right-left > 1) return false;
        return isBalanced(root->left) && isBalanced(root->right);
        
    }
    int Caldepth(TreeNode* node){
        if(node == NULL) return 0;
        int left = Caldepth(node->left)+1;
        int right = Caldepth(node->right)+1;
        return (left>right)?left:right;
    }
};

Optimization Analysis:

In solutions above, there are many repetitive calculation of depth. Actually, unbalance can be recognized in caldepth() function if we use -1 to track this unbalanced state.
Time complexity here is O(n)

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        if(root == NULL) return true;
        int val=Caldepth(root);
        if(val==-1) return false;
        return true;
    }
    int Caldepth(TreeNode* node){
        if(node == NULL) return 0;
        int left = Caldepth(node->left);
        int right = Caldepth(node->right);
        if(left == -1 || right == -1) return -1;
        if(left - right >1 || right - left >1) return -1;
        return (left>right)?left+1:right+1;
    }
};

2015年7月3日星期五

LeetCode: Symmetric Tree

Iteration way:
At first, I think of binary tree level traversal to judge the symmetry with two dequeues. To make sure the symmetry of structure, null element is also needed to record.
finish later

Recursive way:
Use DFS to traverse the tree from two directions, one is data->left->right, the other is data->right->left.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root == NULL) return true;
        return DFS(root->left, root->right);
    }
    
    bool DFS(TreeNode* left, TreeNode* right){
        if(left == NULL && right == NULL) return true;
        if(left == NULL || right == NULL) return false;
        if(left->val != right->val) return false;
        return DFS(left->left, right->right) && DFS(left->right, right->left);
        //not necessary
        /*if(left->left!=NULL && right->right!=NULL) 
            return DFS(left->left, right->right);     
        if(left->right!=NULL && right->left!=NULL)
            return DFS(left->right, right->left);*/
        
    }
};

Reference:
dequeue tutorial
http://fisherlei.blogspot.com/2013/01/leetcode-symmetric-tree.html
http://www.cnblogs.com/TenosDoIt/p/3440729.html

LeetCode: Invert Binary Tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL) return root;
        invert(root);
        return root;
    }
    void invert(TreeNode* node){
        if(node->left == NULL && node->right == NULL) return;
        TreeNode* temp;
        temp=node->left;
        node->left = node->right;
        node->right =temp;
        if(node->left !=NULL) invert(node->left);
        if(node->right !=NULL) invert(node->right);
    }
};

LeetCode: Same Tree

Iteration traversal of binary tree

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if( p==NULL && q==NULL ) return true;
        if( p==NULL || q==NULL ) return false;
        if( p->val  != q->val  ) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

LeetCode: Merge Sorted Array

First try:

Iterate vector nums2 and insert each value into nums1 with bisection search. Time complexity is O(n*log(m))

Here are some explanations for the bisection part:

For line 14 and 15, they ensured that all elements on the left side of left is smaller than destination, while all elements on the right side of right is larger than destination.
即： left左边的都比nums2[i]小，right右边的都比nums2[i]大

when the number is not found, after finishing search, left will be 1 bigger than right, and left and right are adjacent.

To conclude, the searching result will be either a position which is just the position where element equals to destination or a one width range (right, left) that the destination should be located between it. (p.s. left=right+1 here)

So (left-1) or right will be the closet position a little smaller than destination. We need to insert the destination to the left of where value is a little larger than destination. So (eft-1)+1=left is the position to insert. (see line 21)

Line 22 and 23: after each for loop, reset the right to the most right element. Since the number of elements has been changed by insert operation, so ++m. And pop a zero element after insertion in the vector nums2 to make it pass the leetcode test, or there will be unwanted zeros.

My algorithm has the advantage that we don't need to manage the size of vector nums1.

However, this is not the problem designed for. So I have to try again with the standard solution. Orz

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(m==0) {
            nums1=nums2;
            return;
        }
        int left=0;
        int right=m-1;
        int middle=(left+right)/2;
        for(int i=0;i<n;i++){
            while(left<=right){
                middle=(left+right)/2;
                if(nums2[i]<nums1[middle]) right=middle-1;
                if(nums2[i]>nums1[middle]) left=middle+1;
                if(nums2[i]==nums1[middle]) {
                    left=middle;
                    break;
                }
            }
            nums1.insert(nums1.begin()+left,nums2[i]);
            nums1.pop_back();
            right=++m-1;
            //Print vector to testTest 
            /*for(int i=0;i<nums1.size();i++){
              cout<<nums1[i]<<" " ;
              }
              cout<<endl;*/
        }
        
    }
};

Second try:
Comparing two vector from the last element with merge sort.
for process the comparisons between nums1 and nums2.
After that, if nums2 still has elements, keep adding them to nums1.
Time complexity: O(m+n)

Initial ugly codes:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
       //these two special cases are concluded in normal case
        if(m==0) {
            nums1=nums2;
            return;
        }
        if(n==0) return;
        int index1=m-1;
        int index2=n-1;
        int index3=m+n-1;
        while(index1>=0 && index2>=0){
            if( nums1[index1] >= nums2[index2] ){
                nums1[index3]=nums1[index1];
                index3--;
                index1--;
            }
            else{
                nums1[index3]=nums2[index2];
                index3--;
                index2--;
            }
        }
        //can be changed to simple while loop
        if(index1<0){
            for(; index2>=0; index2--){
                nums1[index3]=nums2[index2];
                index3--;
            }
        }
        //codes below are not necessary
        if(index2<0){
            for(; index1>=0;index1--){
                nums1[index3]=nums1[index1];
                index3--;
            }
        }
        
    }
};

Modified version:

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int idx1=m-1;
        int idx2=n-1;
        int idx3=m+n-1;
        while(idx1>=0 && idx2>=0){
            if( nums1[idx1] >= nums2[idx2] ){
                nums1[idx3--]=nums1[idx1--];
            }
            else{
                nums1[idx3--]=nums2[idx2--];
            }
        }
        while(idx2>=0){
            nums1[idx3--]=nums2[idx2--];
        }
    }
};

订阅：博文 (Atom)