求个查找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;
}
}
相关阅读
几次面试才能拿到offer挂靠opt，申请学校去F或G这种大公司对以后职业发展有利吗？面试问到现在工资拿了一家offer还有一周正式上班，又来了第二家更合适的Offer，请教美国的Contract job 和 permanent job究竟差在什么地方最近h1b transfer，几周给结果？non ppopening: front end, full stack, big dataHR打来电话问我想要多少钱［内推］猎豹移动硅谷总部各种职位关于兼职工作工作时长及401K的疑问Salesforce Admin certification 对找工作有帮助吗？vs oracle 认证Python求内推想问一下90天的OPT需要留多少天比较好？Job: Python/JavaScript Developer (sponsor H1B)写代码给别人赚钱的不算牛人资本家需要的就是你们这种无家无国可归的流浪汉问：h4需要保持工作状态么？有没有人会担心给的包裹超出自己的能力太多求教一个F家的 design题目