下午网宿的一个面试题目，当时没有答好。先分析如下：
删除 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 阅读(1245)
评论(0) 编辑 收藏 引用