80 remove duplicates 2 solved (#11)

zwfang · web-flow · commit 698fcb3e8034 · 2018-12-21T15:48:45.000+08:00
diff --git a/README.md b/README.md
@@ -13,6 +13,7 @@ continually updating 😃.
 * [1. Two Sum](./src/0001_two_sum/twosum.go)&nbsp;&nbsp;&nbsp;*`lookup table;`*&nbsp;&nbsp;*`hash table`*
 * [26. Remove Duplicates from Sorted Array](./src/0026_remove_duplicates_from_sorted_array/rdfsa.go)&nbsp;&nbsp;&nbsp;*`double index;`*&nbsp;&nbsp;*`array`*
 * [27. Remove Element](src/0027_remove_element/remove_element.go)&nbsp;&nbsp;&nbsp;*`double index;`*&nbsp;&nbsp;*`array`*
+* [80. Remove Duplicates from Sorted Array II](./src/0080_remove_duplicates_from_sorted_array2/rdfsa2.go)&nbsp;&nbsp;&nbsp;*`double index;`*&nbsp;&nbsp;*`array`*
 * [167. Two Sum II - Input array is sorted](./src/0167_two_sum2/two_sum2.go)&nbsp;&nbsp;&nbsp;*`double index;`*&nbsp;&nbsp;*`binary search`*
 * [209. Minimum Size Subarray Sum](./src/0209_minimum_size_subarray_sum/minimum_size_subarray_sum.go)&nbsp;&nbsp;&nbsp;*`sliding window`*
 * [283. Move Zeroes(solution1)](./src/0283_move_zeroes/move_zeroes.go)&nbsp;&nbsp;&nbsp;*`sliding window`*
diff --git a/src/0080_remove_duplicates_from_sorted_array2/rdfsa2.go b/src/0080_remove_duplicates_from_sorted_array2/rdfsa2.go
@@ -0,0 +1,46 @@
+/*
+80. Remove Duplicates from Sorted Array II
+https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/
+
+Given a sorted array nums, remove the duplicates in-place such that
+duplicates appeared at most twice and return the new length.
+
+Do not allocate extra space for another array, you must do this
+ by modifying the input array in-place with O(1) extra memory.
+*/
+// time: 2018-12-21
+
+package rdfsa2
+
+// double index
+// time complexity: O(n)
+// space complexity: O(1)
+func removeDuplicates(nums []int) int {
+	n := len(nums)
+	if 0 == n || 1 == n {
+		return n
+	}
+
+	var (
+		res   = 2
+		i     = 2
+		index = nextDifferentCharacterIndex(nums, i, 2) // 寻找下一个满足条件的下标
+	)
+
+	for index < n {
+		res++
+		nums[i] = nums[index]
+		i++
+		index = nextDifferentCharacterIndex(nums, i, index+1)
+	}
+	return res
+}
+
+func nextDifferentCharacterIndex(nums []int, j int, p int) int {
+	for ; p < len(nums); p++ {
+		if nums[j-1] == nums[j-2] && nums[p] != nums[j-1] || nums[j-1] != nums[j-2] {
+			break
+		}
+	}
+	return p
+}
diff --git a/src/0080_remove_duplicates_from_sorted_array2/rdfsa2_test.go b/src/0080_remove_duplicates_from_sorted_array2/rdfsa2_test.go
@@ -0,0 +1,22 @@
+package rdfsa2
+
+import "testing"
+
+func TestRemoveDuplicates(t *testing.T) {
+	testCases := [][]int{
+		{1, 1, 1, 2, 2, 3},
+		{1, 2, 2},
+		{0, 0, 1, 1, 1, 1, 2, 3, 3},
+		{},
+		{1},
+		{2, 2},
+		{2, 2, 2},
+	}
+	expected := []int{5, 3, 7, 0, 1, 2, 2}
+
+	for index, data := range testCases {
+		if res := removeDuplicates(data); res != expected[index] {
+			t.Errorf("expected %d, got %d", expected[index], res)
+		}
+	}
+}
diff --git a/src/README.md b/src/README.md
@@ -21,6 +21,7 @@
 |0069|[Sqrt(x)](0069_sqrtx/sqrtx.go)|Easy|*`binary search`*|
 |0070|[Climbing Stairs](./0070_climbing_stairs/climbing_stairs.go)|Easy|*`dynamic programming`*|
 |0076|[Minimum Window Substring](./0076_minimum_window_substring/minimum_window_substring.go)|Hard|*`sliding window`*|
+|0080|[80. Remove Duplicates from Sorted Array II](0080_remove_duplicates_from_sorted_array2/rdfsa2.go)|Medium|*`double index`*|
 |0094|[Binary Tree Inorder Traversal](./0094_binary_tree_inorder_traversal/binary_tree_inorder_traversal.go)|Medium|*`binary tree`*|
 |0100|[Same Tree](./0100_same_tree/same_tree.go)|Easy|*`binary tree`*|
 |0101|[Symmetric Tree](./0101_symmetric_tree/symmetric_tree.go)|Easy|*`stack;`* *`recursion; `* *`iterative`*|
