考试题型

共十道题,前六道是填空题,第七道是简答题,第八道是写出给出程序的输出。

填空题对字符串和指针考察的比较多,大概三道和字符串有关,不是很难。其次虚函数考了两道,函数指针数组一道。第七道简答题给了三个实例,回答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

          https://www.cnblogs.com/zijidan/p/9511235.html