remove element (#9)

zwfang · web-flow · commit d6bd5d8fd66a · 2018-12-20T17:34:11.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`*
+* [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`*
 * [283. Move Zeroes(solution1)](./src/0283_move_zeroes/move_zeroes.go)&nbsp;&nbsp;&nbsp;*`sliding window`*
diff --git a/src/0027_remove_element/remove_element.go b/src/0027_remove_element/remove_element.go
@@ -0,0 +1,47 @@
+/*
+27. Remove Element
+https://leetcode.com/problems/remove-element/
+
+Given an array nums and a value val, remove all instances of that value in-place 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.
+
+The order of elements can be changed. It doesn't matter what you leave beyond the new length.
+*/
+// time: 2018-12-20
+
+package removeelement
+
+// two pointers
+// time complexity: O(n)
+// space complexity: O(1)
+func removeElement(nums []int, val int) int {
+	x := 0
+	for j := 0; j < len(nums); j++ {
+		if nums[j] != val {
+			if x != j {
+				nums[x] = nums[j]
+			}
+			x++
+		}
+	}
+	return x
+}
+
+/*
+func removeElement1(nums []int, val int) int {
+	var (
+		l int
+		r = len(nums)
+	)
+	for l < r {
+		if nums[l] == val {
+			r--
+			nums[l] = nums[r]
+		} else {
+			l++
+		}
+	}
+	return r
+}
+*/
diff --git a/src/0027_remove_element/remove_element_test.go b/src/0027_remove_element/remove_element_test.go
@@ -0,0 +1,13 @@
+package removeelement
+
+import "testing"
+
+func TestRemoveElement(t *testing.T) {
+	nums := []int{0, 1, 2, 2, 3, 0, 4, 2}
+	val := 2
+	expected := 5
+
+	if res := removeElement(nums, val); res != expected {
+		t.Errorf("expected %d, got %d", expected, 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`*|
+|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`*|
 |0061|[Rotate List](./0061_rotate_list/rotate_list.go)|Medium|*`linked list`*|
