Remove Elementの2つの解法

/*************************************************************************
	> File Name: removeElement.cpp
	> Author: CourageK
	> Mail: [email protected]
	> Created Time: 2015 05 11      21 40 41 
Problem Description:
	Given an array and a value, remove all instances of that value in place and return the new length.
	The order of elements can be changed. It doesn't matter what you leave beyond the new length.
 ************************************************************************/

#include
#include
#include
#include
using namespace std;

class Solution
{
public:
/*
 *Solution 1:        ，      O(n)
    int removeElement(vector& nums, int val)
    {
        if(nums.empty()) return 0;
        vector::iterator first = nums.begin();
        vector::iterator last = nums.end();
        //    array    val
        if(find(first, last, val) == last)
            return nums.size(); //          

        //    array   val
        int lenOfNew = 0;
        while(first != nums.end())
        {
            if(*first == val)
            {
                first = nums.erase(first); //      ，first           
                lenOfNew++;
            }
            else first++;
        }
        return nums.size();
    }
*/

    // Solution 2:             ，             ，     (           ,      ：O(n^2)
    int removeElement(vector& nums, int val)
    {
        if(nums.empty()) return 0;
        vector::iterator first = nums.begin();
        vector::iterator last = nums.end();
        //    array    val
        if(find(first, last, val) == last) //     ，      O(n)
            return nums.size(); //          

        //    array   val
        sort(first, last); //              ，             ，     (           ,      ：O(n^2)
        vector::iterator lower = lower_bound(first, last, val); //       val        ,O(logn)
        vector::iterator upper = upper_bound(first, last, val); //        val            ,O(logn)
        nums.erase(lower, upper); //   erase           
        return nums.size();
    }
    
};