《剑指Offer》面试题3

 

问题一、找出数组中重复的数字
  

题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，
也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组{2, 3, 1, 0, 2, 5, 3}，
那么对应的输出是重复的数字2或者3。

 

分析：数组的长度（n）等于数字的范围（0~n-1），如果使用数组下标来定位数组中数字的话，会出现两种情况

没有重复数字：每一个位置刚好对应一个数字，排序后的数组元素的值和下标一一对应

有重复数字：有些位置可能会出现多个数字，有些位置可能没有数字

 

算法思想：重排数组，把元素放置在指定的位置。通过遍历数组的每一个元素，

如果数组元素的值等于下标值，继续遍历下一个元素
如果数组元素的值不等于下标值，根据元素的值找到对应的位置，进行比较，再根据比较结果判断
    比较值相等，找出重复数字，返回
    比较值不等，进行位置交换
继续判断数组元素的值....

 

其他方法：

1.对数组排序，在已排序的数组中扫描重复数字

2.创建哈希表，通过判断新加入的数字在哈希表中是否已存在，来判断重复数字

 

代码

#include "iostream"
using namespace std;


//函数功能：寻找数组中的任意重复数字
//输入参数：numbers[] 源数组、length 数组长度、duplication 重复元素
//返回值： false 没有重复数字、true发现重复数字
bool duplicate(int numbers[], int length, int* duplication)
{
	
	//判断无效参数
	if ( (numbers == nullptr) || (length < 0) )
	{
		return false;
	}

	//判断元素数是否满足
	for (int i = 0; i < length; i++)
	{
		if ( (numbers[i] < 0) || (numbers[i] > length-1) )
		{
			return false;	
		}
	}


	for (int i = 0; i < length; i++)
	{//1.遍历数组
		
		while(i != numbers[i])
		{//2.判断当前值是否等于下标值
			if (numbers[i] == numbers[numbers[i]])
			{//3.判断当前值是否已放置下标位置(判断存在)
				*duplication = numbers[i];	//计入重复元素
				return true;		//4.已存在，返回结果
			}

			//5.交换当前值到下标位置
			int temp = numbers[i];
			numbers[i] = numbers[temp];
			numbers[temp] = temp;
		}
	}
	return false;	//没有找到
}


//进行测试
void test01()
{
	int numbers[] = {2, 3, 1, 0, 2, 5, 3};
	int duplication = 0;
	if ( duplicate(numbers, sizeof(numbers)/sizeof(int), &duplication) == true )
	{
		cout << "res:" << duplication << endl;
	}	
}
int main(int argc, char const *argv[])
{
	test01();
	return 0;
}

运行

 

 

问题二、不修改数组找出重复的数字


题目：在一个长度为n+1的数组里的所有数字都在1到n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2, 3, 5, 4, 3, 2, 6, 7}，那么对应的输出是重复的数字2或者3。

 

分析：数组长度（n+1）大于数字的范围，所以一定有重复的数字。使用二分法的思路，将不断小查找区间的范围，对重复数字进行查找。

 

其他方法：创建一个辅助数组，在辅助数组中查找重复数字，不会破坏原数组的结构。

 

代码

#include "iostream"

using namespace std;

int countRange(const int* numbers, int length, int start, int end);	//统计次数
int getDuplication(const int* numbers, int length);					//查找任意重复数字

//功能:(已知)数组内有重复数字，查找重复数字
//输入:numbers源数组(数字范围1-n)、length数组长度(n+1)
//返回:重复的数字
int getDuplication(const int* numbers, int length)
{
	if ( (numbers == nullptr) || (length <= 0) )
	{//无效参数
		return -1;
	}

	int start = 1;
	int end = length - 1;

	while(start <= end)
	{
		//1.将数字序列所在区间进行二分
		int middle = (end - start)/2 + start;

		//2.统计区间范围的数字的出现次数
		int count = countRange(numbers, length, start, middle);

		//3.判断区间长度是否为1，找出重复数字
		if (start == end)
		{
			if (count > 1)
			{
				return start;
			}
			else
			{
				break;
			}
		}

		//4.重新调整区间，区间内包含重复数字
		if ( count > ((middle - start) + 1) )
		{
			end = middle;
			// end = middle - 1;
		}
		else
		{
			start = middle + 1;
		}

	} 
	return -1;

}


//功能：统计start-end范围的数字的出现次数
//输入：numbers源数组、length数组长度、start，end表示数字范围
int countRange(const int* numbers, int length, int start, int end)
{
	if ( (numbers == nullptr) || (length <= 0) )
	{//无效参数
		return 0;
	}

	int count = 0;
	for (int i = 0; i < length; i++)
	{//遍历数组元素
		if ( (start <= numbers[i]) && (numbers[i] <= end) )
		{
			count++;	//统计次数
		}
	}
	return count;
}

void test01()
{
	int arr[] = {2, 3, 5, 4, 3, 2, 6, 7};
	int res = getDuplication(arr, sizeof(arr)/sizeof(int));
	cout << "res:" << res << endl;
}

int main(int argc, char const *argv[])
{
	test01();
	return 0;
}

 

运行

 

 

总结：面试官提出的需求不同，最终所采用的算法也不相同，这说明面试中和面试官的交流的重要性！！

 

我的码云：https://gitee.com/hinzer/sword_to_offer/tree/master/questions