给无序数组去重

Question

基于26号题目，我发现老师上课讲的都是给有序数组去重的。如果遇见无序数组去重呢？
解决方案是否有两种
1）先给数组排序，在按老师给的方法；
2）遍历数组，每次都检查是否跟前面已去重的元素是否重复。代码如下：

class Solution {//无序数组去重，并返回去重后的数组
public:
	int removeDuplicates(vector<int>& nums) {

		if (nums.size() == 0)
			return 0;

		//nums[1,2,2,1]
		//nums[0...r]去重的
		int r = 0;
		for (int i = 1; i < nums.size(); i++) {
			int isDup = 0;
			for (int j = 0; j <= r; j++) {//判断nums[i]与nums[0...r]是否有重复元素
				if (nums[i] == nums[j]) {//有重复元素
					isDup = 1;
					break;
				}
			}
			if (!isDup) {
				if (r + 1 != i)
					swap(nums[++r], nums[i]);
				else
					++r;
			}
		}
		return r + 1;
	}
};


int main()
{
	vector<int> nums = { 1,2,2,1 };
	cout << Solution().removeDuplicates(nums) << endl;
    std::cout << "Hello World!\n"; 
} 

总结：

1. 我发现无论是1）还是2）两种方案时间复杂度都会达到O(n^2)。老师有更好的思路吗？
   2.还有一个额外的问题，先上代码：

class Solution {
public:
	int removeDuplicates(vector<int>& nums) {

		if (nums.size() == 0)
			return 0;  ///------1）此处不判断，结果不AC
        
		//arr[]={1,1,2}
		//nums[0,,r]去重的
		int r = 0;
		for (int i = 1; i < nums.size(); i++) {
			if (nums[r] != nums[i])
				if (r + 1 != i)
					swap(nums[++r], nums[i]);
				else
					++r;
		}
		return r + 1;
	}
};

1）处不判断不能AC?为什么？

Answer 1

liuyubobobo 2019-09-09 21:52:08

1）

给数组排序，再去重的方式，时间复杂度是 O(nlogn)的。因为给有序数组去重的复杂度是 O(n)的。排序复杂度是O(nlogn)的。整体是O(nlogn + n) = O(nlogn)的。

2）

对无序数组，可以使用一个哈希表（unordered_set），将数组中的元素都扔进哈希表，再取出来，就去重了。时间复杂度O(n)，空间复杂度O(n)。

3）

Leetcode对于错误的提交，会给出致使出错的测试用例。比如你的代码提交给26，返回的是：

红框里的意思就是出错额错误用例，即传入的数组为空数组时出错了。

想想看，为什么？

继续加油！：）