#include <iostream>#include <stdio.h>#include <vector>#include <algorithm>using namespace std;/*問題:Given an array and a value, remove all instances of that value in place and return the new length.Do not allocate extra space for another array, you must do this in place with constant memory.The order of elements can be changed. It doesn't matter what you leave beyond the new length.Example:Given input array nums = [3,2,2,3], val = 3Your function should return length = 2, with the first two elements of nums being 2.分析:此題實際上就是刪除元素為指定值的元素，數組事先是無序的。一種簡單方法是：先排序，排序結束后通過二分查找元素上下區間，刪除區間內元素，時間復雜度為O(N*logN)如果不排序，刪除指定元素，每次從前向后移動，找到指定元素后，將該元素后面所有元素向前移動一位，遍歷元素的時間復雜度為O(N)，找到元素后，后面所有元素向前移動時間復雜度為O(N)，總的時間復雜度為O(N*N)lower_bound:查找元素第一個出現的位置，或者如果沒有該元素，查找大于該元素的位置，使得將元素插入數組后數組仍然有序upper_bound:查找大于元素x的第一個位置，使得如果將待查找元素插入在該位置后，該數組仍然有序輸入:4(元素個數) 3(待刪除元素)3 2 2 3(所有數組元素)4 13 2 2 3輸出:2(新數組的長度)4*/void PRint(vector<int>& nums){if(nums.empty()){cout << "nums is empty" << endl;return ;}int length = nums.size();for(int i = 0 ; i < length ; i++){cout << nums.at(i) << " ";}cout << endl;}class Solution {public: int removeElement(vector<int>& nums, int val) {if(nums.empty()){return 0;}//排序sort(nums.begin() , nums.end());//查找>=元素的第一個出現的位置,位置是迭代器vector<int>::iterator low = lower_bound(nums.begin() , nums.end() , val);//超找>元素第一個出現的位置vector<int>::iterator high = upper_bound(nums.begin() , nums.end() , val);//刪除元素nums.erase(low , high);int length = nums.size();//print(nums);return length; }};void process(){int num;vector<int> datas;int value;int delVal;while(cin >> num >> delVal){datas.clear();for(int i = 0 ; i < num ; i++){cin >> value;datas.push_back(value);}Solution solution;int result = solution.removeElement(datas , delVal);cout << result << endl;}}int main(int argc , char* argv[]){process();getchar();return 0;}
