广州4399面试题(一)
广州4399面试题(一)
By 马冬亮(凝霜 Loki)
一个人的战争(http://blog.csdn.net/MDL13412)
题目描述算法描述现给定一个含有n个元素的数组,请随机获取其中的m个元素(不能重复获取)。
首先,随机获取元素,可以使用rand() % 数组长度;
其次,要保证元素的不重复获取,只需将获取的元素从原数组中移除即可,但是每次都进行删除操作,需要频繁的移动数组元素,其复杂度很高;现在,我们换一种思路,将获取的元素与原数组最后的元素进行交换,再将数组的长度减一,那么就可以做到O(1)复杂度将其移除;详见下图:
程序源码此算法的时间复杂度为O(n),其只与要获取的m个数有关,在n和m相差非常悬殊的时候,效率非常高。
#include <iostream>#include <vector>#include <algorithm>#include <iterator>using namespace std;typedef int ErrorType;const ErrorType ErrSucceed = 0;const ErrorType ErrInvalidRange = 10;const ErrorType ErrUnknown = 100;template <typename ItemType>ErrorType GetRandItemsFromArray(vector<ItemType> &items, const size_t itemCount, vector<ItemType> &result){ // 边界检测 if (items.size() < itemCount) return ErrInvalidRange; // 将结果向量清空,并预留足够的空间,防止多次分配导致的性能开销。 result.clear(); result.reserve(itemCount); // 注意差1的边界错误 size_t itemsLength = items.size() - 1; // 算法描述见正文 for (size_t i = 0; i < itemCount; ++i) { int tmpIndex = rand() % itemsLength; result.push_back(items[tmpIndex]); swap(items[tmpIndex], items[itemsLength]); --itemsLength; } return ErrSucceed;}int main(){ vector<int> vec; for (int i = 0; i < 100; ++i) vec.push_back(i); vector<int> res; for (int i = 0; i < 10; ++i) { GetRandItemsFromArray(vec, 10, res); copy(res.begin(), res.end(), ostream_iterator<int>(cout, " ")); cout << endl; } return 0;}总结
题目本身不难,但是要注意边界的校验,错误处理,代码可读性,数据抽象,时间及空间复杂度。另外,如果是现场写代码,最好问面试官原始数组是否允许修改!