Merge pull request soapyigu#7 from soapyigu/Array

soapyigu · soapyigu · commit d903176d3842 · 2016-04-10T13:09:48.000-07:00
Array
diff --git a/Array/ContainsDuplicate.swift b/Array/ContainsDuplicate.swift
@@ -0,0 +1,27 @@
+/**
+ * Question Link: https://leetcode.com/problems/contains-duplicate/
+ * Primary idea: traverse the array and use a set to check duplicates
+ *
+ * Time Complexity: O(n), Space Complexity: O(n)
+ *
+ */
+
+class ContainsDuplicate {
+    func containsDuplicate(nums: [Int]) -> Bool {
+        if nums.count <= 1 {
+            return false
+        }
+    
+        var set = Set<Int>()
+        
+        for i in 0...nums.count - 1 {
+            if set.contains(nums[i]) {
+                return true
+            } else {
+                set.insert(nums[i])
+            }
+        }
+        
+        return false
+    }
+}
diff --git a/Array/ContainsDuplicateII.swift b/Array/ContainsDuplicateII.swift
@@ -0,0 +1,31 @@
+/**
+ * Question Link: https://leetcode.com/problems/contains-duplicate-ii/
+ * Primary idea: use a dictionary to check duplicates, then judge if their distance is less than k
+ *
+ * Time Complexity: O(n), Space Complexity: O(n)
+ *
+ */
+
+class ContainsDuplicateII {
+    func containsNearbyDuplicate(nums: [Int], _ k: Int) -> Bool {
+        // edge case
+        if nums.count <= 1 {
+            return false
+        }
+        
+        // key: nums[index], value: index
+        var dict = [Int: Int]()
+        
+        for i in 0...nums.count - 1 {
+            if let index = dict[nums[i]] {
+                if i - index <= k {
+                    return true
+                }
+            } 
+            
+            dict[nums[i]] = i
+        }
+        
+        return false
+    }
+}
diff --git a/Array/MoveZeroes.swift b/Array/MoveZeroes.swift
@@ -0,0 +1,29 @@
+/**
+ * Question Link: https://leetcode.com/problems/move-zeroes/
+ * Primary idea: keep index zeroIndex, traverse through the array and swap the value
+ *
+ * Time Complexity: O(n), Space Complexity: O(1)
+ *
+ */
+
+class MoveZeroes {
+    func moveZeroes(inout nums: [Int]) {
+        var zeroIndex = 0
+        var left = 0
+        let right = nums.count
+        
+        while left < right {
+            if nums[left] != 0 {
+                _swap(&nums, zeroIndex, left)
+                zeroIndex += 1
+            }
+            left += 1
+        }
+    }
+    
+    private func _swap(inout nums: [Int], _ p: Int, _ q: Int) {
+        let temp = nums[p]
+        nums[p] = nums[q]
+        nums[q] = temp
+    }
+}
diff --git a/Array/RemoveDuplicatesFromSortedArray.swift b/Array/RemoveDuplicatesFromSortedArray.swift
@@ -11,7 +11,7 @@ class RemoveDuplicatesFromSortedArray {
             return nums.count
         }
     
-        var lastIndex: Int = 0
+        var lastIndex = 0
         
         for i in 1...nums.count - 1 {
             if nums[i] != nums[lastIndex] {
diff --git a/Array/RemoveElement.swift b/Array/RemoveElement.swift
@@ -0,0 +1,25 @@
+/**
+ * Question Link: https://leetcode.com/problems/remove-element/
+ * Primary idea: keep a index, compare the element at that index with val while moving forward
+ * Time Complexity: O(n), Space Complexity: O(1)
+ *
+ */
+
+class RemoveElement {
+    func removeElement(inout nums: [Int], _ val: Int) -> Int {
+        var lastIndex = 0
+        
+        if nums.count == 0 {
+            return lastIndex
+        }
+        
+        for i in 0...nums.count - 1 {
+            if nums[i] != val {
+                nums[lastIndex] = nums[i]
+                lastIndex += 1
+            }
+        }
+        
+        return lastIndex
+    }
+}
diff --git a/Array/RotateArray.swift b/Array/RotateArray.swift
@@ -34,7 +34,7 @@ class RotateArray {
     }
     
     private func _swap(inout nums: [Int], _ p: Int, _ q: Int) {
-        var temp: Int = nums[p]
+        var temp = nums[p]
         nums[p] = nums[q]
         nums[q] = temp
     }

Original file line number	Diff line number	Diff line change
`@@ -11,7 +11,7 @@ class RemoveDuplicatesFromSortedArray {`
`11`	`11`	`return nums.count`
`12`	`12`	`}`
`13`	`13`
`14`		`- var lastIndex: Int = 0`
	`14`	`+ var lastIndex = 0`
`15`	`15`
`16`	`16`	`for i in 1...nums.count - 1 {`
`17`	`17`	`if nums[i] != nums[lastIndex] {`
Original file line number	Diff line number	Diff line change
`@@ -34,7 +34,7 @@ class RotateArray {`
`34`	`34`	`}`
`35`	`35`
`36`	`36`	`private func _swap(inout nums: [Int], _ p: Int, _ q: Int) {`
`37`		`- var temp: Int = nums[p]`
	`37`	`+ var temp = nums[p]`
`38`	`38`	`nums[p] = nums[q]`
`39`	`39`	`nums[q] = temp`
`40`	`40`	`}`