w*****t
发帖数: 485 | 1 不记得是哪家的了：
给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个算法
快速查找这个值。
求拐点值，如: "1,2,3,4,5,4,3,2,1", --> 5
"1,1,1,1,1,2,1,1" --> 2
"1,2,1,1,1,1,1,1" --> 2
有 log(N)的解法吗？ | l******n
发帖数: 9344 | 2 做一阶difference
b(i)=a(i+1)-a(i)
然后二分就可以了
【在 w*****t 的大作中提到】
: 不记得是哪家的了：
: 给定一个函数，f(x),x在某值之前是非递减的，在某值之后是非递增的。设计一个算法
: 快速查找这个值。
: 求拐点值，如: "1,2,3,4,5,4,3,2,1", --> 5
: "1,1,1,1,1,2,1,1" --> 2
: "1,2,1,1,1,1,1,1" --> 2
: 有 log(N)的解法吗？
| x****g
发帖数: 1512 | 3 有点晕.
如果做过a(i+1)-a(i)就已经是O(N)了.
再二分意义何在?
直接二分不行吗?
【在 l******n 的大作中提到】
: 做一阶difference
: b(i)=a(i+1)-a(i)
: 然后二分就可以了
| c*****e
发帖数: 67 | 4 直接二分：
left和right先skip掉相同的数，
然后left, right取mid，看mid的左[mid-1]右[mid+1]：
如果左右都小，则找到；
如果左小右大，则在非递减部分，更新left=mid+1
如果左大右小，则在非递增部分，更新right=mid-1
贴个js代码不知道有没有bug，有的话麻烦提一下：
function turnPoint(a) {
var left = 0,
right = a.length - 1,
mid,
len = a.length;
while (left <= right) {
while (left <= right && a[left + 1] == a[left]) left++;
while (left <= right && a[right - 1] == a[right]) right--;
mid = (left + right) / 2;
if (mid > 0 && mid + 1 < len) {
if (a[mid - 1] < a[mid] && a[mid + 1] < a[mid])
return a[mid];
else if (a[mid - 1] < a[mid] && a[mid] < a[mid + 1])
left = mid + 1;
else if (a[mid - 1] > a[mid] && a[mid] > a[mid + 1])
right = mid - 1;
}
}
return -1;
}
console.log(turnPoint([1,2,3,4,5,4,3,2,1]));
console.log(turnPoint([1,1,1,1,1,2,1,1]));
console.log(turnPoint([1,2,1,1,1,1,1,1])); | h*********o
发帖数: 230 | 5 有dup就不work了吧
【在 c*****e 的大作中提到】
: 直接二分：
: left和right先skip掉相同的数，
: 然后left, right取mid，看mid的左[mid-1]右[mid+1]：
: 如果左右都小，则找到；
: 如果左小右大，则在非递减部分，更新left=mid+1
: 如果左大右小，则在非递增部分，更新right=mid-1
: 贴个js代码不知道有没有bug，有的话麻烦提一下：
: function turnPoint(a) {
: var left = 0,
: right = a.length - 1,
| l*********d
发帖数: 78 | | s********x
发帖数: 81 | 7 好像确实是没有, average case下, 肯定用binary search.
但是在worse case下, 是O(N). 一个特别长的数列, 所有元素都是1, 除了第二个元素
是2
left, mid, right
left < mid && mid < right, 点在mid和right之间
left < mid && mid = right, 两边都有可能
left < mid && mid > right, 两边都有可能
left = mid && mid < right, 点在mid和right之间
left = mid && mid = right, 两边都有可能
left = mid && mid > right, 两边都有可能
left > mid && mid < right, 不可能
left > mid && mid = right, 点在left和mid之间
left > mid && mid > right, 点在left和mid之间 | z******g
发帖数: 271 | | w*****t
发帖数: 485 | 9 这个解法不错，思路是对的！
不过这个代码对一些边界没有处理:
比如只有一个元素时，left+1会越界
"if (mid > 0 && mid + 1 < len)", 如果这个条件不满足，会导致死循环
【在 c*****e 的大作中提到】
: 直接二分：
: left和right先skip掉相同的数，
: 然后left, right取mid，看mid的左[mid-1]右[mid+1]：
: 如果左右都小，则找到；
: 如果左小右大，则在非递减部分，更新left=mid+1
: 如果左大右小，则在非递增部分，更新right=mid-1
: 贴个js代码不知道有没有bug，有的话麻烦提一下：
: function turnPoint(a) {
: var left = 0,
: right = a.length - 1,
| c*****e
发帖数: 67 | 10 嗯写得太快没写完整，只默认为输入是存在拐点的。
如果考虑上各种不存在拐点的情况：
1. 边界那里的确粗心了，应该是left+1<=right和left<=right-1
2. 加个判断避免死循环：
while (left + 1 <= right && a[left + 1] == a[left]) left++;
while (left <= right - 1 && a[right - 1] == a[right]) right--;
if (left == right) return -1;
【在 w*****t 的大作中提到】
: 这个解法不错，思路是对的！
: 不过这个代码对一些边界没有处理:
: 比如只有一个元素时，left+1会越界
: "if (mid > 0 && mid + 1 < len)", 如果这个条件不满足，会导致死循环
|
|
