狗家电面

可以用xor  index+1 和 num 进行xor 当结果是0的时候就找到了

为什么我觉得第二个case解是2呢？
题意说最小index，而且没规定生序或者降序

哇 跟我的题简直一样

fentoyal 发表于 2018-1-4 03:23
握手，看了ls用sum的, 我以为就我这么想呢。。

很屌！！请问原理是什么啊 请教大佬

先从后往前遍历第一次，维护一个最小堆；再从前往后遍历第二次，维护一个最大堆；在第二次遍历的时候，当最大堆的top小于最小堆的top时候return此时的index，否则最小堆弹出top并放入最大堆中。

我有个思路。找到的这个index，一定满足 max(A[0 to index] ) < min(A[index + 1 to N]),所以开一个int[] left保存从左往右的最大值，再开一个int[] right保存从右往左的最小值，然后选出 left[index] <= right[index + 1]那个index

九零 发表于 2018-1-4 03:15
当前位置数组的最大值

请问层主能举个例子吗，不是很理解，谢谢

fentoyal 发表于 2018-1-4 03:13
贡献个我的思路，很简洁， 大家看对不对：

请问层主能说一下思路吗，不是很理解算法，谢谢

wjw779 发表于 2018-1-19 16:56
请问层主能说一下思路吗，不是很理解算法，谢谢

按题目要求，其实就是数组可以分两份，满足 左边最大的 <右边最小，且 分割点坐标尽可能小。
分割点坐标尽可能小这个简单，就从左往右找分割点就行了。

关键说左边最大的 <右边最小
如果是一个普通数组，这个一趟遍历O(1)空间应该是不行的（没证明，直觉）。
但条件是数组数是1 ～ n, 那可以利用一下：
比如说这个数组：
2 3 5 X X X
当你看到5时，你不看后面是啥，是不是可以立刻知道，最终答案（分割点）坐标（1-base坐标）肯定>=5了。
所以原理就是你坐标i = 你从左边数到i的最大值时，则i是一个合理的分割点：比如
2 3 5 4 1 6 7 8
到1时，1左边最大为5,1的坐标也是5（第5个，idx=4）那这5个数就是自成一体的。如果1左边最大为7：
2 3 7 4 1 6 5  8
那想让左边包含全部1到7的数字，分割点至少在7,所以得继续往右走到5,这时坐标为7,最大为7,找到分割点。

dengzeyu147 发表于 2018-1-13 23:01
很屌！！请问原理是什么啊 请教大佬

我在ls的回帖里简单说了下。