剑指Offer: 面试题3:数组中重复的数字

题目1

找出数组中重复的数字。

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

解题思路

  • 排序(时间复杂度为O(nlogn),空间复杂度为O(1)或O(n),具体根据实现算法)
  • 哈希表(时间复杂度为O(n),空间复杂度为O(n))
  • 时间复杂度为O(n),空间复杂度为O(1)的算法

最优算法

#include <iostream>
#include <vector>
#include <algorithm>

bool FindDuplication(std::vector<int>, int*);

int main(int argc, char* argv[])
{
	std::vector<int> iv({2,3,1,0,2,5,3});
	int dupl = 0;
	bool rst = FindDuplication(iv, &dupl);
	return 0;
}

bool FindDuplication(std::vector<int> numbers, int* duplication)
{
	int len = numbers.size();
	int idx = 0;
	if (len == 0)
		return false;
	for (auto& i : numbers)
	{
		if (i < 0 || i > len)
			return false;
	}
	for (auto i = numbers.begin(); i != numbers.end(); ++i, ++idx)
	{
		while (*i != idx)
		{
			if (*i == numbers.at(*i))
			{
				*duplication = *i;
				return true;
			}
			std::iter_swap(i, i + (*i - idx)); // 必须使用std::iter_swap,不能使用std::swap
		}
	}
	return false;
}

 

题目2

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

最优算法

#include <iostream>
#include <vector>
#include <algorithm>

bool FindDuplicationNoEdit(std::vector<int>, int*);
int CountRange(std::vector<int>, int, int);

int main()
{
	std::vector<int> iv({2,3,5,4,3,2,6,7});
	int duplication = 0;
	bool rst = FindDuplicationNoEdit(iv, &duplication);
	return 0;
}

bool FindDuplicationNoEdit(std::vector<int> numbers, int* duplication)
{
	int len = numbers.size();
	int start = 1;
	int end = len - 1;
	if (len <= 0)
		return false;
	while (start != end)
	{
		int middle = (start + end) >> 1;
		int count = CountRange(numbers, start, middle);
		if (middle == start && count > 1)
		{
			*duplication = start;
			return true;
		}
		if (count > middle - start + 1)
		{
			end = middle;
		}
		else
		{
			start = middle;
		}
	}
	return false;
}

int CountRange(std::vector<int> numbers, int start, int end)
{
	int cnt = 0;
	for (auto& i : numbers)
	{
		if (i >= start && i <= end)
			++cnt;
	}
	return cnt;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

3 × 3 =

65 + = 73