编程 6

Leetcode – Search in Rotated Sorted Array II编程

By admin in 编程 on 2019年10月8日

编程 1Paste_Image.png

编程 2Paste_Image.png

My code:

My code:

My code:

public class Solution { public int findDuplicate(int[] nums) { if (nums == null || nums.length == 0) return -1; int begin = 1; int end = nums.length; while (begin < end) { int mid = begin + (end - begin) / 2; int counter = 0; for (int i = 0; i < nums.length; i++) if (nums[i] <= mid) counter++; if (counter > mid) end = mid; else begin = mid + 1; } return begin; }}
public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; return search(0, nums.length - 1, nums, target); } private boolean search(int begin, int end, int[] nums, int target) { if (begin > end) return false; else { int mid = (begin + end) / 2; if (nums[mid] > nums[end]) { // left is sorted if (nums[mid] < target) { int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (nums[mid] > target) { if (nums[begin] > target) { // in the right int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (nums[begin] == target) return true; else { // in the left int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin + 1, i, nums, target); } } else return true; } else if (nums[mid] < nums[end]) { // right is sorted if (nums[mid] > target) { int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin, i, nums, target); } else if (nums[mid] < target) { if (target < nums[end]) { int i = mid + 1; while (i <= end && nums[i] == nums[i - 1]) i++; if (i >= nums.length) return false; else return search(i, end, nums, target); } else if (target > nums[end]) { int i = mid - 1; while (i >= begin && nums[i] == nums[i + 1]) i--; if  return false; else return search(begin, i, nums, target); } else return true; } else return true; } else if (nums[mid] == target) return true; else return search(begin, end - 1, nums, target); } }}
public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) return 0; int minIndex = 0; for (int i = 1; i < nums.length; i++) { if (nums[i] >= nums[i - 1]) continue; else { minIndex = i; break; } } return nums[minIndex]; }}

这道题目我没能想出来。感觉有点考智商。那个想法我的确没想出来。首先贴一个博文。

My test result:

My test result:

然后这道题目有O
的做法。但是感觉思路太复杂了。就忽略了。然后思考了下他的第二种做法,
O举个例子:假设n = 9那么,有10个位置放入1-9肯定会有重复。取中间值 1 + /
2 = 5;在1-9中, <= 5
的应该有5个,假设不重复。但是如果1-5之间有数字重复了,那么,就应该大于5个了。所以,遍历下整个数组,统计
<=5 的个数,如果大于5,那么就表示,那个重复的数字,他的值v , 1 <=
v <= 5也就是begin <= v <= mid反之,则是:mid + 1 <= v <=
end于是采用binary search
的思想,一步步往下缩小范围。最终,就能把v限定在一个确定值里面,此时,begin
= end所以,最终可以找到这个值。

编程 3

编程 4

**总结: 不在是binary search array, 而是 通过 binary search
来限定一个可能性取值的范围。最终达到目的。**

这道题目还是和前面的差不多。然后就是要用while循环把重复的数字跳到。然后就是同样的注意点,当nums[mid]
= nums[end]
时,可能出现两种情况,右侧已经排序好或者左侧已经排序好。所以不能确定。于是,就直接将end

这不是一个好方法。下面介绍 binary search 版方法。

Anyway, Good luck, Richardo!

  • 1,重新进行搜索。所以,如果数组数字都是一样的,需要进行
    O复杂度,而不再是之前的binary search 的 O

My code:

My cdoe:

**总结: Array, binary search**

public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) return 0; int minIndex = findMin(0, nums.length - 1, nums); return nums[minIndex]; } private int findMin(int begin, int end, int[] nums) { if (begin == end) return begin; int mid = (begin + end) / 2; if (nums[mid] < nums[end]) // right part is sorted so minimun exists in the left return findMin(begin, mid, nums); else // left part is sorted so minimun exists in the right return findMin(mid + 1, end, nums); }}
public class Solution { public int findDuplicate(int[] nums) { if (nums == null || nums.length == 0) return -1; int begin = 1; int end = nums.length -1; // end = n while (begin < end) { int target = (begin + end) / 2; int count = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] >= begin && nums[i] <= target) count++; } if (count > target - begin + 1) { end = target; } else { begin = target + 1; } } return begin; }}

Anyway, Good luck, Richardo!

My test result:

寒假在家效率实在太低。这道题目再做也还是没有做出来。shit思路还是听巧妙地。Anyway,
Good luck, Richardo!

My code:

编程 5Paste_Image.png

My code:

public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) return false; int begin = 0; int end = nums.length - 1; while (begin <= end) { int middle = (begin + end) / 2; if (nums[middle] < nums[end]) { // right part is sorted if (target < nums[middle]) { end = middle - 1; } else if (target == nums[middle]) { return true; } else if (target <= nums[end]) { begin = middle + 1; } else { end = middle - 1; } } else if (nums[middle] > nums[end]) { // left part is sorted if (target > nums[middle]) { begin = middle + 1; } else if (target == nums[middle]) { return true; } else if (target >= nums[0]) { end = middle - 1; } else { begin = middle + 1; } } else { if (target == nums[middle]) return true; else end = end - 1; } } return false; }}

一下子快了好多。上一种算法复杂度是O, 而这个复杂度是
O上一个算法就是从头遍历,找到突然开始变小的位置,就是最小值。仔细介绍该算法。

public class Solution { public int findDuplicate(int[] nums) { if (nums == null || nums.length == 0) { return -1; } int i = 0; while (i < nums.length) { if (nums[nums[i] - 1] != nums[i]) { int temp = nums[nums[i] - 1]; nums[nums[i] - 1] = nums[i]; nums[i] = temp; } else if (nums[i] - 1 == i) { i++; continue; } else { return nums[i]; } } return -1; }}

差不多的题目。就把之前的情况细分。nums[middle] <
nums[end]nums[middle] > nums[end]nums[middle] == nums[end]
-> end –
1差不多。然后因为出现了重复元素所以可以滑动,用while循环加速。但是我懒得写了。第一次的版本是写了的。

编程 6

这道题目的思想和

Anyway, Good luck, Richardo!

如上图所示:

然后看了下以前的做法,也是真的巧妙啊。感觉复杂度也是O啊 ?

提供一种新的思路就是直接traverse, 复杂度是 O上面的做法, time
complexity: best: O, worst: O

当 nums[mid] > nums[end]
时,表示,左侧已经排好序了,右侧没有,最小值一定出现在右侧。当
nums[mid] < nums[end]
时,表示,右侧已经排好序了,左侧没有,最小值一定出现在左侧。

Anyway, Good luck, Richardo! — 09/01/2016

Anyway, Good luck, Richardo! — 08/12/2016

然后利用这个规则,还用 binary search
的思想,不断递归,直到找到最小值。算法复杂度是 O

最新的做法不太对。因为我修改了原数组。这是不允许的。所以一开始的做法才是正确的。

My code:

**总结: Array, Binary Search**

Anyway, Good luck, Richardo! — 09/11/2016

public class Solution { public boolean search(int[] nums, int target) { if (nums == null || nums.length == 0) { return false; } int begin = 0; int end = nums.length - 1; while (begin <= end) { int mid = begin + (end - begin) / 2; if (target == nums[mid]) { return true; } else if (nums[begin] < nums[mid]) { // left is sorted if (nums[begin] <= target && target < nums[mid]) { end = mid - 1; } else { begin = mid + 1; } } else if (nums[begin] > nums[mid]) { // right is sorted if (nums[mid] < target && target <= nums[end]) { begin = mid + 1; } else { end = mid - 1; } } else { begin++; } } return false; }}

Anyway, Good luck, Richardo!

reference:

My code:

much simpler code

public class Solution { public int findMin(int[] nums) { if (nums == null || nums.length == 0) return 0; int begin = 0; int end = nums.length - 1; while (begin < end) { int middle = (begin + end) / 2; if (nums[middle] < nums[end]) { end = middle; } else { // nums[middle] >= nums[end] which means nums[middle] is not the absolute minimum elem begin = middle + 1; } } return nums[begin]; }}

首先判断,左右那个部分是 sorted ,然后再进行下一步。

没什么难的。主要在一个地方思考了下。当 nums[middle] <
nums[end]时,end = middle.But, 当nums[middle] >= nums[end]时,
begin = middle + 1,
因为nums[middle]一定不是唯一的那个最小值。所以可以排除他,进一步缩小范围。

Anyway, Good luck, Richardo! — 09/21/2016

Anyway, Good luck, Richardo!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 澳门新葡亰官网app 版权所有