remove duplicate from sorted array solved

zwfang · zwfang · commit ba1ceeed4ba5 · 2018-12-20T18:36:34.000+08:00
diff --git a/README.md b/README.md
@@ -11,6 +11,7 @@ continually updating 😃.
 
 ### Array
 * [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`*
 * [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`*
diff --git a/src/0026_remove_duplicates_from_sorted_array/rdfsa.go b/src/0026_remove_duplicates_from_sorted_array/rdfsa.go
@@ -0,0 +1,45 @@
+/*
+26. Remove Duplicates from Sorted Array
+https://leetcode.com/problems/remove-duplicates-from-sorted-array/
+
+Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.
+*/
+// time: 2018-12-20
+
+package rdfsa
+
+// double index
+// time complexity: O(n)
+// space complexity: O(1)
+func removeDuplicates(nums []int) int {
+	n := len(nums)
+
+	if 0 == n {
+		return n
+	}
+
+	var (
+		res   = 1
+		i     = 1
+		index = nextDifferentCharacterIndex(nums, 1) // 下一个不重复的地址
+	)
+
+	for index < n {
+		res++
+		nums[i] = nums[index]
+		i++
+		index = nextDifferentCharacterIndex(nums, index+1)
+	}
+	return res
+}
+
+func nextDifferentCharacterIndex(nums []int, p int) int {
+	for ; p < len(nums); p++ {
+		if nums[p] != nums[p-1] {
+			break
+		}
+	}
+	return p
+}
diff --git a/src/0026_remove_duplicates_from_sorted_array/rdfsa_test.go b/src/0026_remove_duplicates_from_sorted_array/rdfsa_test.go
@@ -0,0 +1,19 @@
+package rdfsa
+
+import "testing"
+
+func TestRemoveDuplicates(t *testing.T) {
+	// removeDuplicates([]int{0, 0, 1, 1, 1, 2, 2, 3, 3, 4})
+	testCases := [][]int{
+		{1, 1, 2},
+		{0, 0, 1, 1, 1, 2, 2, 3, 3, 4},
+	}
+
+	expected := []int{2, 5}
+
+	for index, data := range testCases {
+		if res := removeDuplicates(data); expected[index] != res {
+			t.Errorf("expected %d, got %d", expected[index], res)
+		}
+	}
+}
diff --git a/src/README.md b/src/README.md
@@ -9,6 +9,7 @@
 |0020|[Valid Parentheses](0020_valid_parentheses/valid_parentheses.go)|Easy|*`string;`* *`stack`*|
 |0021|[Merge Two Sorted Lists](0021_merge_two_sorted_lists/mergeTwoLists.go)|Easy|*`linked list`*|
 |0025|[Reverse Nodes in k-Group](./0025_reverse_nodes_in_k_group/reverse_node_k_group.go)|Hard|*`linked list`*|
+|0026|[Remove Duplicates from Sorted Array](0026_remove_duplicates_from_sorted_array/rdfsa.go)|Easy|*`array;`*  *`double index`*|
 |0027|[Remove Element](0027_remove_element/remove_element.go)|Easy|*`array`*|
 |0033|[Search in Rotated Sorted Array](0033_search_in_rotated_sorted_array/search_in_rotated_sorted_array.go)|Medium|*`binary search`*|
 |0034|[ Find First and Last Position of Element in Sorted Array](0034_find_first_and_last_position_of_element_in_sorted_array/find_first_and_last_position_of_element_in_sorted_array.go)|Medium|*`binary search`*|
