week4 assignment-2 update NOTE.md&T33

SpongeMa · SpongeMa · commit f4e4e241fe77 · 2020-07-06T17:10:58.000+08:00
diff --git a/Week04/33.search.js b/Week04/33.search.js
@@ -42,39 +42,86 @@
  * @param {number} target
  * @return {number}
  */
+/**@sponge
+ * 解法一：暴力
+ * 思路：将给定的数组还原成排序数组，再进行二分查找。
+ * 但如果单纯用暴力解法还原数组需要从头到尾遍历所以需要O(n)的时间复杂度，可用下面方法简化成O(logn)
+ * 1.找到第一个无序的位置还原成排序数组，用O(logn)实现，
+ * 2.再用二分查找O(logn)
+ * time:O(logn)
+ * space:O(1)
+ * runtime:72ms 56%
+ * memory usage:33.3MB 100%
+ */
+var search = function (nums, target) {
+  if (!nums.length) return -1;
+
+  let l = 0;
+  let r = nums.length - 1;
+  let mid = 0;
+  //暴力还原排序数组,找到第一个无序的位置(用二分查找实现)
+  while (l < r) {
+    mid = Math.floor((l + r) / 2);
+    if (nums[mid] > nums[r]) {
+      l = mid + 1;
+    } else {
+      r = mid;
+    }
+  }
+  //找到第一个无序的位置，即最小的值
+  let min = l;
+  l = 0;
+  r = nums.length - 1;
+  //判断target是否在min~r之间
+  if (target <= nums[r]) l = min;
+  else r = min - 1;
+  //按二分查找模板搜索target
+  while (l <= r) {
+    mid = Math.floor((l + r) / 2);
+    if (nums[mid] == target) return mid;
+    if (nums[mid] < target) l = mid + 1;
+    else r = mid - 1;
+  }
+  return -1;
+};
 
 /**@sponge
- * 解法一：二分查找
- * 根据nums[mid]与nums[l]的关系判断mid在左段还是右段
+ * 解法二：二分查找
+ * 根据nums[mid]与nums[r]的关系判断mid在左段还是右段,
+ * 或者nums[mid]与nums[l]的关系判断mid在左段还是右段
  * 再判断target是在mid的左边还是右边
  * time:O(logn)
  * space:O(1)
+ * runtime:72ms 
+ * memory usage:33.1MB
  */
-var search = function(nums, target) {
+var search = function (nums, target) {
+  if (!nums.length) return -1;
+
   let l = 0;
-  let r = nums.length-1;
+  let r = nums.length - 1;
 
-  while (l<=r) {
-    let mid = Math.floor((l+r)/2);
-    if (target==nums[mid]) return mid;
-    // 先根据 nums[mid] 与 nums[lo] 的关系判断 mid 是在左段还是右段 
-    if (nums[mid] >= nums[l]) {
-      // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 lo 和 hi
-      if (target >= nums[l] && target < nums[mid]) {
-          r = mid - 1;
+  while (l <= r) {
+    let mid = Math.floor((l + r) / 2);
+    if (target == nums[mid]) return mid;
+    // 先根据 nums[mid] 与 nums[r] 的关系判断 mid 是在左段还是右段 
+    if (nums[mid] < nums[r]) {
+      // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 l 和 r
+      // mid ~ r 之间有序
+      if (target > nums[mid] && target <= nums[r]) {
+        l = mid + 1;
       } else {
-          l = mid + 1;
+        r = mid - 1;
       }
     } else {
-      if (target > nums[mid] && target <= nums[r]) {
-          l = mid + 1;
+      if (target < nums[mid] && target >= nums[l]) {
+        r = mid - 1;
       } else {
-          r = mid - 1;
+        l = mid + 1;
       }
-  }
-    
+    }
+
   }
   return -1;
 };
-// @lc code=end
-
+// @lc code=end
diff --git a/Week04/NOTE.md b/Week04/NOTE.md
@@ -111,10 +111,8 @@ def DFS(self, tree):
 一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好方法。由于贪心法的高效性以及其所求得得答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些结果不那么精确的问题。
 
 - 近似算法
-
-- - 判断近似算法的优劣标准如下：
-
-  - - 速度有多快
+  - 判断近似算法的优劣标准如下：
+    - 速度有多快
     - 得到的近似解与最优解的接近程度
 
 可以用来求图中的最小生成树、哈夫曼编码等。
@@ -133,38 +131,26 @@ def DFS(self, tree):
 
 
 
-#### [33. 搜索旋转排序数组](https://leetcode-cn.com/problems/search-in-rotated-sorted-array/)
-
-暴力解法
-
-思路：将给定的数组还原成排序数组，再进行二分查找。
+#### **练习：**
 
-但如果单纯用暴力解法还原数组需要从头到尾遍历所以需要O(n)的时间复杂度，可用下面方法简化成O(logn)
+使用二分查找，寻找一个半有序数组 [4, 5, 6, 7, 0, 1, 2] 中间无序的地方
+**思路：**
 
-1.找到第一个无序的位置还原成排序数组，用O(logn)实现。
-
-2.再用二分查找O(logn)。
+- 找到第一个无序的地方，即找到最小的值
 
 ```javascript
-var search = function(nums, target) {
- if(!nums.length) return -1;
-
+var search = function(nums) {
  let l = 0;
  let r = nums.length - 1;
- let mid = 0;
-
- //暴力还原排序数组,即找到第一个无序的位置(用二分查找实现)
- while (l<=r) {
+ let mid = Math.floor((l+r)/2);
+ while (l < r) {
+  //如果nums[mid] > nums[r]，说明mid~r之间无序，所以l要mid的右边移动继续查找最小值
+  if (nums[mid] > nums[r]) l=mid+1;
+  //否则r
+  else r = mid;
   mid = Math.floor((l+r)/2);
-  if (nums[mid]>nums[mid+1])
-   break;
-  if (nums[mid]>=nums[l]) { 
-   l = mid + 1;
-  }else {
-   r = mid - 1;
-  }
  }
- return -1;
-}
+ return mid;
+};
 ```
 
