Remove Duplicates from Sorted Array——移除排序數組中重復元素

Remove Duplicates from Sorted Array——移除排序數組中重復元素

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array A = [1,1,2],

Your function should return length = 2, and A is now [1,2].

思路：

（1）這道題其實很簡單。主要是因為數組已經是排好順序的。如果不仔細看題目，把數組當作無序數組進行操作，OJ時會顯示超時。

（2）題目要求是不能申請二額外空間，如果提交時有申請額外空間，也是不通過的。

（3）還需要注意的一個地方是，數組中元素的位置不能改變。比如對於數組[1,1,1,4,5]，移除重復元素後為[1,4,5]，起始數字為1，而不能是其它數字。

（4）我們只需對對組遍歷一次，並設置一個計數器，每當遍歷前後元素不相同，計數器加1，並將計數器對應在數組中位置定位到當前遍歷的元素。

算法代碼實現如下：

public static int removeDuplicates(int[] A) {
	int len = A.length;
	if (len == 0)
		return 0;
	int count = 1;
	for (int i = 1; i < len; i++) {
		if (A[i] == A[i - 1]) {
			continue;
		}else{
			A[count] = A[i];
			count++;
		}
	}
	return count;
}

思路：

（1）如果不允許申請額外空間，則可以先對數組進行排序，為了提高效率一般考慮使用快速排序，然後再參照上面有序數組進行操作；

（2）如果允許申請空間，則只需創建一個HashSet，遍歷一次數組，通過contanins()方法進行判斷就能得到結果。

（1）和（2）所對應代碼如下所示（注：針對本文所示的題目，如果用下面代碼進行OJ，（1）會超時，（2）會產生額外空間）：

不可以申請額外空間：

public static int removeDuplicates(int[] A) {
	int len = A.length;
	if (len == 0)
		return 0;

	quickSort(A, 0, len - 1);

	int count = 1;
	for (int i = 1; i < len; i++) {
		if (A[i] == A[i - 1]) {
			continue;
		} else {
			A[count] = A[i];
			count++;
		}
	}
	return count;
}

//快速排序
private static void quickSort(int[] table, int low, int high) {
	if (low < high) {
		int i = low, j = high;
		int vot = table[i];
		while (i != j) {
			while (i < j && vot <= table[j])
				j--;
			if (i < j) {
				table[i] = table[j];
				i++;
			}
			while (i < j && table[i] < vot)
				i++;
			if (i < j) {
				table[j] = table[i];
				j--;
			}
		}
		table[i] = vot;
		quickSort(table, low, j - 1);
		quickSort(table, i + 1, high);
	}
}

可以申請額外空間：（其中，HashSet的contains()方法是用來過濾重復元素的）

public static int removeDuplicates(int[] A) {
	int len = A.length;
	HashSet set = new HashSet();
	for (int i = 0; i < len; i++) {
		if (set.size() == 0) {
			set.add(A[i]);
		}
		if (!set.contains(A[i])) {
			set.add(A[i]);
		}
	}
	return set.size();
}