下午網宿的一個面試題目，當時沒有答好。先分析如下：
刪除 vector 中大于 n 的數，注意 vector 中并不一定存在 n + 1
最簡單的做法是循環，逐個掃描，到檢查到有大于 n 的元素時，移動后面的元素。這里有另種掃描方式，分別是從左到右和從右到左。
從右到左的方式效率更高，因為避免了移動其他大于 n 的元素。但是兩種方式的時間復雜度都是 O(N ^ 2)。
可以通過先排序然后找到第一個大于 n 的元素的迭代器，然后刪除該迭代器到最后一個元素之間的元素。
但是這種方法改變原來小于等于 n 的元素之間的相對順序。
查找第一個大于 n 的元素的迭代器是先要排序，然后查找。
查找的方法有，直接循環遍歷查找。也可以傳一個函數，用 find_if。也可以用函數對象，函數對象的函數時你可以自己設定想要的參數，還是用 find_if 查找。
這種方法的時間復雜度是 O(NlogN)。
第三種方法是利用 remove_if 函數，但是 remove_if 函數不會真的刪除元素，需要借助于 erase 函數。但是 remove_if 操作的效率和第一種是一樣的，時間復雜度還是 O(N^2)。
實現：
1 #include <iostream>
2 #include <vector>
3 #include <algorithm>
4 using namespace std;
5
6 // 從左向右掃描刪除移動
7 void delLeftToRight(vector<int>& data, int n)
8 {
9 for (size_t i = 0; i < data.size(); ++i)
10 {
11 if (data[i] > n)
12 {
13 for (size_t j = i + 1; j < data.size(); ++j)
14 {
15 data[j - 1] = data[j];
16 }
17 data.pop_back();
18 --i;
19 }
20 }
21 }
22
23 // 從右向左掃描刪除移動
24 void delRightToLeft(vector<int>& data, int n)
25 {
26 for (size_t i = data.size(); i > 0; --i)
27 {
28 if (data[i - 1] > n)
29 {
30 for (size_t j = i; j < data.size(); ++j)
31 {
32 data[j - 1] = data[j];
33 }
34 data.pop_back();
35 }
36 }
37 }
38
39 // 排序，順序遍歷查找，刪除
40 void delSort(vector<int>& data, int n)
41 {
42 sort(data.begin(), data.end());
43 vector<int>::const_iterator cit = data.begin();
44 for (; cit != data.end(); ++cit)
45 {
46 if (*cit > n)
47 {
48 break;
49 }
50 }
51 data.erase(cit, data.end());
52 }
53
54 class biggerN
55 {
56 int m;
57 public:
58 biggerN(int i) : m(i) {}
59 bool operator ()(int n)
60 {
61 return n > m;
62 }
63 };
64
65 bool bigger(int n)
66 {
67 return n > 10;
68 }
69
70 // 排序，查找，刪除
71 void delSortFind(vector<int>& data, int n)
72 {
73 sort(data.begin(), data.end());
74 vector<int>::const_iterator cit;
75 cit = find_if(data.begin(), data.end(), biggerN(n));
76 // cit = find_if(data.begin(), data.end(), bigger);
77 data.erase(cit, data.end());
78 }
79
80 // 移動，刪除
81 void delRemove(vector<int>& data, int n)
82 {
83 data.erase(remove_if(data.begin(), data.end(), biggerN(n)), data.end());
84 // data.erase(remove(data.begin(), data.end(), 20), data.end());
85 }
86
87 void display(const vector<int>& data)
88 {
89 for (size_t i = 0; i < data.size(); ++i)
90 {
91 cout << data[i] << ' ';
92 }
93 cout << endl;
94 }
95
96 int main()
97 {
98 vector<int> data;
99 for (int i = 20; i > 0; --i)
100 {
101 data.push_back(i);
102 }
103 // data.push_back(20);
104 display(data);
105 // delLeftToRight(data, 10);
106 // delRightToLeft(data, 10);
107 // delSort(data, 10);
108 // delSortFind(data, 10);
109 delRemove(data, 10);
110 display(data);
111 }
posted on 2011-05-21 00:18
unixfy 閱讀(1257)
評論(0) 編輯 收藏 引用