Move zeros to end C++

Given an unsorted integer array, place all zeros to the end of the array without changing the sequence of non-zero elements. (i.e. [1,3,0,8,12, 0, 4, 0,7] --> [1,3,8,12,4,7,0,0,0])

思路：用个index记录当前需要填充的位置，扫一遍就行了，跟quicksort思路一致。复杂度O(n)

0. void pushzeros(int A[], int n){  
1.   
2.   int index = 0;  
3.   
4.   for(int i = 0; i < n; i++){  
5.   
6.     if(A[i] != 0){  
7.          int tmp = A[index];  
8.   
9.          A[index++] = A[i];  
10.   
11.          A[i] = tmp;  
12.   
13.     }  
14.      
15.   }     
16.   
17. }   

sort colors(c++)

Leetcode Sort Colors
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library’s sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0′s, 1′s, and 2′s, then overwrite array with total number of 0′s, then 1′s and followed by 2′s.
Could you come up with an one-pass algorithm using only constant space?
思路：就是quicksort的思路了。

1.   void swap(int &i, int &j){  
2.    int temp = i;  
3.    i = j;  
4.    j = temp;  
5. }  
6.   
7. void sortColors(int A[], int n) {  
8.   int rindex = 0,bindex = n-1;  
9.   int i = 0;  
10.   while(i <= bindex){  
11.     if(A[i] == 0) {  
12.       swap(A[i],A[rindex]);rindex++;  
13.     }  
14.     if(A[i] == 2) {  
15.       swap(A[i],A[bindex]); bindex--;  
16.     }  
17.     else i++;  
18.   }   
19. }  

merge sorted array(C++ code)

leetcode Merge Sorted ArrayMay 20 '12
Given two sorted integer arrays A and B, merge B into A as one sorted array.
Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

0. void merge(int A[], int m, int B[], int n) {  
1.   
2.        if(n == 0) return;  
3.   
4.        int i = m+n-1;  
5.   
6.       while(m > 0 && n > 0){  
7.   
8.            if(A[m-1] > B[n-1]) {A[i--] = A[m-- -1]; }  
9.   
10.            else{  
11.   
12.               A[i--] = B[n-- -1];   
13.   
14.            }  
15.   
16.       }   
17.   
18.      while(m > 0) {A[i--] = A[m-- -1]; }      
19.   
20.      while(n > 0) {A[i--] = B[n-- -1]; }   
21.   
22.        }  

Insert Interval (C++ code)

LeetCode Insert Interval, Mar 27 '12
 难度4，出现频率5
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
 思路： 我写的这个好复杂呀。。(后面有简单的)
* struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
       int from =0, to =0,i,left,right;

 if(intervals.empty() || newInterval.end < intervals[0].start){

      intervals.insert(intervals.begin(), newInterval);

      return intervals;

}

if(newInterval.start > intervals.back().end){

  intervals.push_back(newInterval);

  return intervals;

}

      for(i = 0; i < intervals.size(); i++){

         if(newInterval.start < intervals[i].start){

             if(i > 0 && newInterval.start <= intervals[i-1].end) {

                from = i-1;

                left = intervals[i-1].start;

             }

             else{

               from = i;

               left = newInterval.start;

            }

             break;

        }
        from = i;
        left = intervals[i].start;

    }

     for(i = from; i < intervals.size(); i++){

         if(newInterval.end < intervals[i].end){

            if(i > 0 && newInterval.end < intervals[i].start) {

              to = i - 1;

              right =newInterval.end;

            }

          else{

             to = i;

             right = intervals[i].end;

          }
          break;

        }
        to = i;
        right = newInterval.end;

    }

Interval *toadd = new Interval(left,right);  

intervals.erase(intervals.begin() + from, intervals.begin() + to + 1);

intervals.insert(intervals.begin() + from, *toadd);

return intervals;
    }


简单版： 为毛别人能写的如此简单呢，学习~~下面这个是从luckynoob那里看来的（稍作修改）。

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 

   vector<Interval> res; 
   int i=0;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      res.push_back(intervals[i++]);
 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
 
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end);
 
   res.push_back(newInterval); 
 
   while(i < intervals.size())
 
      res.push_back(intervals[i++]);
 
 return res;
 
} 

然后我又写了个修改输入array不需要额外空间的： 

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {    
   int i=0, from, to;
   int n = intervals.size(); 
 
   while(i < n && newInterval.start > intervals[i].end)
      i++;
   from = i; 
   if(i < n) newInterval.start = min(newInterval.start, intervals[i].start);
 
   while( i < n && newInterval.end >= intervals[i].start ) 
        i++;
   to = i - 1;
   if(i > 0) newInterval.end =  max(newInterval.end, intervals[i-1].end); 
 
   if(from <= to) intervals.erase(intervals.begin()+ from, intervals.begin()+ to + 1);

   intervals.insert(intervals.begin()+from, newInterval); 

  
 return intervals;
 
}   

       

First Missing Positive (C++ code)

LeetCode First Missing Positive, Mar 8 '12

 难度5，出现频率2

Given an unsorted integer array, find the first missing positive integer.
For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.
Your algorithm should run in O(n) time and uses constant space.
 52741
思路：一共n个数，所以first missing positive最大为n+1.从头检查每个数，如果该数i满足1<=i<=n,则把该数放在a[i-1]里。这样放完后再检查一遍，当遇到a[i] != i+1，return i+1。如果a[i] = i+1 for 0<=i<=n-1,则返回n+1.

int firstMissingPositive(int A[], int n) {
   int i;
  for(i = 0; i < n; i++){
         int temp = A[i];

    while( temp <= n && temp >= 1 && temp != i + 1 && A[temp-1] != temp){

         A[i] = A[A[i] - 1];

         A[temp-1] = temp;
       
         temp = A[i];
       

    }

  }

  for(i = 0; i < n; i++){

    if(A[i] != i + 1) return i+1;

  }

  return n+1;



}