leetcode 第136题 c++

leetcode 第136题 c++

先用排序做法

//排序做法
int singleNumber(vector& nums) {
	if (nums.size() == 1) return nums[0];

	sort(nums.begin(), nums.end());

	int temp = nums[0];
	int count = 1;
	for (int i = 1; i < nums.size(); i++)
	{
		if (nums[i] != temp ){
			if (count == 1){
				return temp;
			}else{
				//重置
				count = 1;
				temp = nums[i];
			}
		}
		else{
			count++;
			temp = nums[i];
		}
	}
	return temp;
}

非排序做法，采用map

//非排序做法
int singleNumber(vector& nums) {
	if (nums.size() == 1) return nums[0];

	map res;
	map::iterator itor;
	for (int i = 0; i < nums.size(); i++)
	{
		if(res.find(nums[i]) != res.end()){
			//如果找到了
			itor = res.find(nums[i]);
			itor->second++;
		}
		else{
			res.insert(make_pair(nums[i], 1));
		}
	}

	map::iterator itor1;
	for (itor1 = res.begin(); itor1 != res.end(); itor1++)
	{
		if (itor1->second == 1){
			return itor1->first;
		}
	}
	return -1;
}