考试题型
共十道题，前六道是填空题,第七道是简答题，第八道是写出给出程序的输出。
填空题对字符串和指针考察的比较多，大概三道和字符串有关，不是很难。其次虚函数考了两道，函数指针数组一道。第七道简答题给了三个实例，回答const的在不同情况下的用法；第八道题考的也是虚函数问题，没什么可说的；第九道用伪代码写出行列式求解的算法流程，第十题有两问，第一问找出一个int 数组中重复的数字，第二问要求对自己上一问写的代码进行优化，只写出思路即可。
下面主要回顾一下最后一题。
题目：在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组，假设数组中只有一个相同数字。例如，如果输入长度为5的数组{1,2,3,4,2}，那么对应的输出是重复的数字2。
思路1：借鉴二分查找的思想，将数字1~n拆分成1~m和m+1~n两部分，如果数字范围1~m中数字个数大于m，则重复数字在1~m中间，否则重复数字一定在数字范围m+1~n中，算法复杂度为O(nlogn)。
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int duplication(vector<int> vec)
{
// 空数组
int length = vec.size();
if (vec.size() == 0)
return -1;
// 数字超界
for (int i = 0; i < length; ++i)
{
if (vec[i]<1 || vec[i]>length - 1)
return -1;
}
// 定义数字范围
int begin = 1;
int end = length - 1;
// 指定数字范围内的数字个数
while (begin <= end)
{
// 计算数字范围的中点
int mid = (begin + end) >> 1;
// 统计指定数字范围内的数字个数
int count = countrange(vec, begin, mid, length);
if (end > begin)
{
// 更新数字范围
if (count > (mid - begin + 1))
end = mid;
else
begin = mid + 1;
}
else
{
if (count > 1)
return begin;
else
break;
}
}
return -1;
}
int countrange(vector<int> vec, int begin, int end, int length)
{
int count = 0;
for (int i = 0; i < length; ++i)
{
if (vec[i] >= begin && vec[i] <= end)
++count;
}
return count;
}
};
int main()
{
vector<int> vec;
vector<int> vec1 = { 1,2,3,4,5,6,7 };
vector<int> vec2 = { 1,1,2,3,4,5,6 };
vector<int> vec3 = { 2,2,3,3,4,5,6 };
Solution solution;
cout << solution.duplication(vec) << endl;
cout << solution.duplication(vec1) << endl;
cout << solution.duplication(vec2) << endl;
cout << solution.duplication(vec3) << endl;
return 0;
}
/*
输出：
-1
-1
1
3
*/ 思路2：利用类似于桶排序的原理，数组中的所有数字都为0到n-1，可以把这些数字当做数组下标，数值用来统计个数，即i为下标，a[i]为个数，如果a[i]>1，则i为相应的重复数字。时间复杂度为O（n），空间复杂度为O（n）。
#include<iostream>
using namespace std;
bool func(int a[], int length, int *result)
{
/*错误判断省略*/
int map[255] = { 0 };
for (int i = 0; i < length; i++)
{
map[a[i]]++;
}
for (int i = 0; i < length; i++)
{
if (map[i] > 1)
{
*result = i;
return true;
}
}
return false;
}
int main()
{
int a[] = { 1,2,3,4,4,5,6 };
int length = sizeof(a) / sizeof(int);
int *result = a;
func(a, length,result);
cout << *result << endl;
return 0;
}
/*
输出：
4
*/ 思路3：如果一个长度为n，值为0到n-1，且没有重复的数组，i从0到n-1，对应的a[0]到a[n-1]不会指向同一个a[i]两次。这里，对于i，先让a[a[i]]加上一数组长度length，如果后面这个i再次出现，那么a[a[i]]必定比length大，那么i就位重复的数。算法复杂度为O(1)。
#include<iostream>
using namespace std;
//a为该数组 length为数组长度 result为找到的一个重复数字
int func(int numbers[], int length)
{
for (int i = 0; i < length; i++) {
int index = numbers[i];
if (index >= length) {
index -= length;
}
if (numbers[index] >= length) {
return index;
}
numbers[index] = numbers[index] + length;
}
return -1;
}
int main()
{
int a[] = { 1,2,3,4,4,5,6 };
int length = sizeof(a) / sizeof(int);
int *result = a;
cout << func(a, length);
return 0;
}
/*
输出：
4
*/ 参考：https://blog.csdn.net/qq_32957239/article/details/80500183
京公网安备 11010502036488号