不修改数组找出重复的数字

• 前言
• 一、示例
• 二、代码解析
• • 1.新建.cpp文件
  • • 代码如下（示例）：
  • 2.测试

---

前言

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

---

一、示例

示例 1：

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

二、代码解析

1.新建.cpp文件

代码如下（示例）：

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



#include <iostream>
#include<vector>
#include<unordered_map>
using namespace std;

/*{2,3,5,4,3,2,6,7}*/
int countRange(const int* numbers, int length, int start, int end)
{
	if (numbers == nullptr)
	{
		return 0;
	}
	int count = 0;
	for (int i = 0; i < length; ++i)
	{
		if (numbers[i] >= start && numbers[i] <= end)
		{
			++count;
		}
	}
	return count;
}
/*法一---二分法*/
int GetDuplication1(const int* numbers, int length)
{
	if (numbers == nullptr)
	{
		return -1;
	}
	int start = 1;
	int end = length - 1;
	while (end >= start)
	{
		int middle = ((end - start) >> 1) + start;
		int count = countRange(numbers, length, start, middle);
		/*cout << "start = " << start << " ";
		cout << "middle = " << middle << " ";
		cout << "end = " << end << " ";
		cout << "count = " << count << endl;*/
		if (end == start)
		{
			if (count > 1)
			{
				return start;
			}
			else
			{
				break;
			}
		}
		if (count > (middle - start + 1))
		{
			end = middle;
		}
		else
		{
			start = middle + 1;
		}
	}
	return -1;
}

/*法二---哈希表*/
int GetDuplication2(vector<int>& nums)
{
	if (nums.empty())return -1;
	unordered_map<int, int> mapNums;
	int result = -1;
	for (int num : nums)
	{
		mapNums[num]++;
		if (mapNums[num] == 2)
		{
			result = num;
			break;
		}
	}
	return result;
}

/*法三---辅助数组*/
int GetDuplication3(vector<int>& nums)
{
	if (nums.empty())return -1;
	int len = nums.size();
	vector<int> tmp(len, -1);
	int result = -1;
	for (int i = 0; i < len; ++i)
	{
		if (tmp[nums[i]] == -1)
		{
			tmp[nums[i]] = nums[i];
		}
		else
		{
			result = nums[i];
			break;
		}
	}
	return result;
}

int main()
{
	int numbers[8] = { 2,3,5,4,3,2,6,7 };
	vector<int> nums = { 2,3,5,4,3,2,6,7 };
	cout << "二分法----->" << GetDuplication1(numbers, 8) << endl;
	cout << "哈希表----->" << GetDuplication2(nums) << endl;
	cout << "辅助数组----->" << GetDuplication3(nums) << endl;
	return 0;
}

2.测试