求个查找turn point的binary search code# JobHunting - 待字闺中
t*n
1 楼
[555555555555555555555555125555]
能找上面这个array turn point 的BS算法. 先谢谢了.
能找上面这个array turn point 的BS算法. 先谢谢了.
c*2
2 楼
BS是指logn么? 貌似不可能吧
l*n
3 楼
返回数组记录turning point值和位置。
static int[] turning(int[] arr) {
return turning(arr, 0, arr.length);
}
static int[] turning(int[] arr, int i, int j) {
if (j == i)
return new int[] { Integer.MAX_VALUE, -1 };
if (j - i == 1 || arr[j - 1] > arr[i])
return new int[] { arr[i], i };
int m = (i + j) / 2;
if (arr[m] < arr[i]) {
return turning(arr, i + 1, m + 1);
} else if (arr[m] > arr[i]) {
return turning(arr, m + 1, j);
} else {
int[] l = turning(arr, i, m);
int[] r = turning(arr, m + 1, j);
return l[0] <= r[0] ? l : r;
}
}
static int[] turning(int[] arr) {
return turning(arr, 0, arr.length);
}
static int[] turning(int[] arr, int i, int j) {
if (j == i)
return new int[] { Integer.MAX_VALUE, -1 };
if (j - i == 1 || arr[j - 1] > arr[i])
return new int[] { arr[i], i };
int m = (i + j) / 2;
if (arr[m] < arr[i]) {
return turning(arr, i + 1, m + 1);
} else if (arr[m] > arr[i]) {
return turning(arr, m + 1, j);
} else {
int[] l = turning(arr, i, m);
int[] r = turning(arr, m + 1, j);
return l[0] <= r[0] ? l : r;
}
}
相关阅读
在现在的公司只工作了不到两个月跳槽twitter支持EB1B?/话说这次FB没破发，各位偷着乐吧据了。。。心情复杂。。。也轻松了。。。求职业规划建议讨论一道L的validate binary tree和求深度的问题Job-hunting 台湾实验区发展研究中心招聘海外人才目录大家作决定，consulting公司和博士后选哪个？公司工作工资会无限增长吗？onsite两个礼拜没有消息如果对同一组的两个role都有兴趣，是不是可以两个都申？EAD卡一般多久收到？Position of Trust designation 是什么？Help: Does it mean the interview is cancelled?做题做得很郁闷，求指点Facebook Prices at $38 With Trading Set to Start Friday该如何解释，急大家都是准备很充分了再投还是边投边准备？nonprofit h1b to profit h1b 回国问题H1B filing这算成功了吗？