C++ 算法（一）

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

int duplicateInArray0(vector<int>& nums) {
	//暴力 n*n
	int n = nums.size();
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = i + 1; j < n; j++)
		{
			if (nums[i] ^ nums[j] == 0)
				return nums[i];
		}
	}

	return 0;
}

int duplicateInArray(vector<int>& nums) {
	//二分 n* logn
	int l = 1, r = nums.size() - 1;
	while (l < r)
	{
		int mid = l + r >> 1; //[l, mid] [mid+ 1, r]
		int count = 0;
		for (int i = 0; i < nums.size(); i++)
		{
			if (nums[i] >= l && nums[i] <= mid)
				count++;
		}
		if (count > mid - l + 1) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main()
{
	int a[8] = { 2, 3, 5, 4, 3, 2, 6, 7 };
	vector<int> nums;
	//将a的所有元素插入到b中
	nums.insert(nums.begin(), a, a + 9);
	cout << "暴力解答：" << duplicateInArray(nums) << endl;
	cout << "二分解答：" << duplicateInArray(nums) << endl;
	return 0;

}