qinyafee
diff --git a/‎algorithms/cpp/constructBinaryTreeFromPreorderAndInorderTraversal/105.construct-binary-tree-from-inorder-and-postorder-traversal.png
275 KB b/‎algorithms/cpp/constructBinaryTreeFromPreorderAndInorderTraversal/105.construct-binary-tree-from-inorder-and-postorder-traversal.png
275 KB
diff --git a/‎algorithms/cpp/constructBinaryTreeFromPreorderAndInorderTraversal/constructBinaryTreeFromPreorderAndInorderTraversal.cpp
Lines changed: 1 addition & 0 deletions b/‎algorithms/cpp/constructBinaryTreeFromPreorderAndInorderTraversal/constructBinaryTreeFromPreorderAndInorderTraversal.cpp
Lines changed: 1 addition & 0 deletions
diff --git a/‎algorithms/cpp/removeDuplicatesFromSortedArray/removeDuplicatesFromSortedArray.cpp
Lines changed: 60 additions & 35 deletions b/‎algorithms/cpp/removeDuplicatesFromSortedArray/removeDuplicatesFromSortedArray.cpp
Lines changed: 60 additions & 35 deletions
@@ -1,6 +1,7 @@
 // 递归
 // 保证元素无重复
 // 前序遍历中的第一个节点就是根节点
+// 无论前序/中序，左/右子树节点相等
 //链接：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/solution/cong-qian-xu-yu-zhong-xu-bian-li-xu-lie-gou-zao-9/
 // time O(n), space O(n)
 class Solution {
 
@@ -2,46 +2,71 @@
 // Author : Hao Chen
 // Date   : 2014-06-22
 
-/********************************************************************************** 
-* 
-* 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].
-* 
-*               
-**********************************************************************************/
+/**********************************************************************************
+ *
+ * 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].
+ *
+ *
+ **********************************************************************************/
 // my implm
+// 双指针
 class Solution {
-public:
-    int removeDuplicates(vector<int>& nums) {
-        if(nums.empty()) return 0;
-        int i = 0; //输出结果index
-        for(int j = 1; j < nums.size(); ++j){
-            if(nums[i] == nums[j]) continue;
-            else nums[++i] = nums[j];
-        }
-        return i+1;
+ public:
+  int removeDuplicates(vector<int>& nums) {
+    if (nums.empty()) {
+      return 0;
     }
+    int i = 0;  //输出结果index
+    for (int j = 1; j < nums.size(); ++j) {
+      if (nums[i] == nums[j]) {
+        continue;
+      } else {
+        nums[++i] = nums[j];
+      }
+    }
+    return i + 1;
+  }
 };
 
+// 变种：如果数组未排序，输出结果数组。[1,3,4,2,2,2,1,5] ->[1, 3, 4, 2, 5]
+// 哈希+双指针
+void removeDuplicates(vector<int>& nums) {
+  unordered_set<int> st;
+
+  int i = 0;
+  for (int j = 0; j < nums.size(); ++j) {
+    if (st.find(nums[j]) != st.end()) {
+      continue;
+    } else {
+      st.insert(nums[j]);
+      nums[i++] = nums[j];
+    }
+  }
+  nums.erase(nums.begin() + i, nums.end());
+  // for (const auto &x : nums) {
+  //   cout << x << ", ";
+  // }
+}
+
 class Solution {
-public:
-    int removeDuplicates(int A[], int n) {
-        
-        if (n<=1) return n;
-        
-        int pos=0;
-        for(int i=0; i<n-1; i++){
-            if (A[i]!=A[i+1]){
-                A[++pos] = A[i+1];
-            }
-        }
-        return pos+1;
+ public:
+  int removeDuplicates(int A[], int n) {
+    if (n <= 1) return n;
+
+    int pos = 0;
+    for (int i = 0; i < n - 1; i++) {
+      if (A[i] != A[i + 1]) {
+        A[++pos] = A[i + 1];
+      }
     }
+    return pos + 1;
+  }
 };