SmallestRotationWithHighestScore [source code]
public class SmallestRotationWithHighestScore {
static
/******************************************************************************/
class Solution {
public int bestRotation(int[] A) {
int N = A.length;
int[] bad = new int[N];
for (int i = 0; i < N; i++) {
int left = (i - A[i] + 1 + N) % N, right = (i + N + 1) % N;
bad[left]--;
bad[right]++;
if (left > right)
bad[0]--;
}
int sum = 0, max_i = -1, max_sum = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
sum += bad[i];
if (sum > max_sum) {
max_sum = sum;
max_i = i;
}
}
return max_i;
}
// i:(0), num:(2), 4, 1
// i:(1), num:(3), 4, 2
// i:(2), num:(1), 2, 3
// i:(3), num:(4), 0, 4
// i:(4), num:(0), 0, 0
// [[-3, 1, 0, 1, -1]]
}
/******************************************************************************/
public static void main(String[] args) {
SmallestRotationWithHighestScore.Solution tester = new SmallestRotationWithHighestScore.Solution();
int[][] inputs = {
{2, 3, 1, 4, 0}, {3},
};
for (int i = 0; i < inputs.length / 2; i++) {
System.out.println (Printer.separator ());
int[] A = inputs[2 * i];
int ans = inputs[2 * i + 1][0], output = tester.bestRotation (A);
System.out.printf ("%s -> %s, expected: %d\n",
Printer.array (A), Printer.wrap (output + "", output == ans ? 92 : 91), ans
);
}
}
}
不简单的题目, uwi这题用了半个小时;
笨办法肯定就是直接所有的K都尝试一次(因为是返回smallest的, 所以实际上超过N的K就不用尝试了(虽然mod之后是相等的));
题目给的两个case的解释比较简单, 这个时候不要大意, 实际上我还并没有理解人逻辑, 所以自己尝试人逻辑走一遍看看能不能有什么新的想法;
一个看起来不naive的办法:
因为这样就不用真的去shift, 因为shift本身操作速度太慢了; 不过你仔细看你给的这个方法, 其实也是N^2的方法; 尝试一下看看能不能AC?
写出来这个代码:
class Solution {
public int bestRotation(int[] A) {
int max_i = Integer.MAX_VALUE, max_score = -1, N = A.length;
for (int i = 0; i < N; i++) {
int score = 0;
for (int j = 0; j < N; j++) {
if (A[(i + j) % N] <= j)
score++;
}
if (score > max_score) {
max_i = i;
max_score = score;
}
}
return max_i;
}
}
好不意外的TLE了;
然后这里观察到一个东西, 这里我们做的内容, 实际上非常类似strstr, 是不是? 所以是不是可能利用KMP的优化?
不过好像也不一样啊, 这里我们的pattern是text一半的长度, 这种情况下, KMP的那种prefix优化, 真的能够达到很好的效果吗?
完全没有思路, 不想了;
自己模仿editorial写了一下, 写的过程中, 感觉如果自己第一步, 直接对于每一个数字, 找到所有不好的index, 类似这样:
好像有所帮助, 这样起码一个bad area, good area对分的思路还是稍微容易看出来一点了;
而且这个图画出来之后发现一个问题: 哪有什么wrap around? 几乎都是只有一个区间的啊; 也就是说, 对于一个数字的bad interval, 是不可能出现不连续的情况的;
哦不对, 我漏掉了一个东西, 这个是bad indices, 我们在bad里面要统计的应该是bad shifts; 如果算上这个, 最后是可能有需要wrap的情况的;
不过话说回来, 如果bad indices都联系, 是不是说明, 如果我们允许shift成为负值, 那么最后也可以用连续的方式来表达一个bad shift的区间;
不过如果允许负的shift, 一个问题就是, 上下限的上限是多少? 这个就是一个很烦人的问题了; 所以感觉shift还是从0开始是最好的;
另外自己尝试去写的时候才发现, 这个left和right的计算公式好像并不是那么直接明显的样子, 一时半会儿还是感觉想不到;
继续观察这个图:
好像除了0以外的A[i], 反正最少都可以往左走到尽头, 所以这个可能就是为什么他这里right这么计算(注意, right对应的是大值, 因为我们现在在找的其实是shift的范围而不是index的范围);
所以原来的做法的核心就是, left位置是很好理解的, 如果A[i]现在在left的左边, 那么最后得到的shift bad区间就有wrap, 而如果现在A[i]本身就已经在对应的left的右边了, 那么在走到right(也就是走到index 0)之前, 我们其实就已经走到了shift left, 所以这个时候就是对应的left <= right的时候, 比如如果A[5] = 2, 这种, left就是5 - 2 = 3, right就是i = 5; 你可能会想, 除了0以外的数字, 如果shift i, 那么肯定就走到index 0了, 那么这个时候肯定是bad的, 但是在index 0..i之间, 能保证全都是bad吗? 关键是, 我们从来没有保证过这个! 最大的shift bad是i, 但是最小的未必是0; 如果是0, 就是有wrap的情况, 如果没有wrap, 那么在0..right之间, 一定有一个left, 0..left-1的shift对应的index, 不是bad的;
所以这个算法作者的总结真的是很不错的;
另外discussion第一解法的observation也能对应的看出来了, 他就是看出来了, right始终对应的就是index等于0的位置, 很固定的一个东西, 所以干脆就不计算了;
真正自己写这个算法的时候, 就当做没有wrap的时候, 先写算式, 脑子里要有这个感觉, 就算是最后有了wrap, 最后数学上还是能够统一的; 事实上, 我认为原来的作者就是这样做的, 不然为什么会命名叫做left和right呢, 对应的就是这个意思;
后来想想, 干脆判断A[i]在i的左边还是右边, 分情况讨论是不是好处理一些? 这里这种统一的写法, 感觉真正面试的时候掌握不好, 太容易翻车了;
right计算的实际上不是bad shift区间的右边inclusive端点, 而是再加一个的exclusive的端点, 这个下面说过了, 是interval counting对应的技巧; 不过right计算的时候为什么就要把这个+1代进去? 这个是因为这样可以使用mod N的操作: 如果你直接计算right = i % N, 然后你后面使用right + 1, 是完全有可能出界的;
速度是11ms (45%);
editorial
Approach #1: Interval Stabbing [Accepted]
Intuition
Say N = 10 and A[2] = 5. Then there are 5 rotations that are bad for this number: rotation indexes 0, 1, 2, 8, 9 - these rotations will cause this number to not get 1 point later.
In general, for each number in the array, we can map out what rotation indexes will be bad for this number. It will always be a region of one interval, possibly two if the interval wraps around (eg. 8, 9, 0, 1, 2 wraps around, to become [8, 9] and [0, 1, 2].)
At the end of plotting these intervals, we need to know which rotation index has the least intervals overlapping it - this one is the answer.
大概的思路应该是这个意思:
Algorithm
First, an element like A[2] = 5 will not get score in (up to) 5 posiitons: when the 5 is at final index 0, 1, 2, 3, or 4. When we shift by 2, we'll get final index 0. If we shift 5-1 = 4 before this, this element will end up at final index 4. In general (modulo N), a shift of i - A[i] + 1 to i will be the rotation indexes that will make A[i] not score a point.
If we are trying to plot an interval like [2, 3, 4], then instead of doing bad[2]--; bad[3]--; bad[4]--;, what we will do instead is keep track of the cumulative total: bad[2]--; bad[5]++. For "wrap-around" intervals like [8, 9, 0, 1, 2], we will keep track of this as two separate intervals: bad[8]--, bad[10]++, bad[0]--, bad[3]++. (Actually, because of our implementation, we don't need to remember the bad[10]++ part.)
At the end, we want to find a rotation index with the least intervals overlapping. We'll maintain a cumulative total cur representing how many intervals are currently overlapping our current rotation index, then update it as we step through each rotation index.
class Solution {
public int bestRotation(int[] A) {
int N = A.length;
int[] bad = new int[N];
for (int i = 0; i < N; ++i) {
int left = (i - A[i] + 1 + N) % N;
int right = (i + 1) % N;
bad[left]--;
bad[right]++;
if (left > right)
bad[0]--;
}
int best = -N;
int ans = 0, cur = 0;
for (int i = 0; i < N; ++i) {
cur += bad[i];
if (cur > best) {
best = cur;
ans = i;
}
}
return ans;
}
}
没有看懂, 先print一个trace:
Your input
[2,3,1,4,0]
Your stdout
i:(0), left:(4), right:(1), [[-1, 1, 0, 0, -1]]
i:(1), left:(4), right:(2), [[-2, 1, 1, 0, -2]]
i:(2), left:(2), right:(3), [[-2, 1, 0, 1, -2]]
i:(3), left:(0), right:(4), [[-3, 1, 0, 1, -1]]
i:(4), left:(0), right:(0), [[-3, 1, 0, 1, -1]]
然后大概画画看:
没有完全画完, 不过大概意思应该还是理解的;
下面要解决的一个问题, 就是他这个cumulative counting是怎么运行的; 首先这个做法的目的很明确, 因为这里每次更新都是一个interval(连续)所有的entry全都更新, 而这里这个cumulative做法实现了之后, 你对于每一个interval的更新, 只要对两个端点进行更新就行了, 这个对于最后提升复杂度肯定是帮助很大;
感觉这个方法以前是不是见过? 好像有一个interval类的问题当中确实是碰到过;
现在的问题是, 感觉还不是很确定这个办法真的correct, 所以尝试理解一下他的正确性;
大概脱离这个问题先理解一下这个方法的总体做法;
可以看到, 用这种-1 +1的思路来表达一个interval, 最后很容易的就可以找到交集最多的一个点;
然后我改一下这题的程序:
class Solution {
public int bestRotation(int[] A) {
int N = A.length;
int[] bad = new int[N], real_bad = new int[N];
for (int i = 0; i < N; ++i) {
int left = (i - A[i] + 1 + N) % N;
int right = (i + 1) % N;
bad[left]--;
bad[right]++;
if (left != right) updateRealBad (real_bad, left, right - 1);
if (left > right)
bad[0]--;
}
int best = -N;
int ans = 0, cur = 0;
for (int i = 0; i < N; ++i) {
cur += bad[i];
if (cur > best) {
best = cur;
ans = i;
}
}
return ans;
}
void updateRealBad (int[] real_bad, int left, int right) {
if (left <= right) {
for (int i = left; i <= right; i++)
real_bad[i]--;
} else {
updateRealBad (real_bad, 0, right);
updateRealBad (real_bad, left, real_bad.length - 1);
}
}
}
打印一个trace(不应用这个cumulative interval的方法的count放在real_count里面):
Your input
[2,3,1,4,0]
Your stdout
i:(0), left:(4), right:(1), [[0, 0, 0, 0, 0]]
i:(0), left:(4), right:(1), [[-1, 1, 0, 0, -1]], real: [[-1, 0, 0, 0, -1]]
i:(1), left:(4), right:(2), [[-1, 1, 0, 0, -1]]
i:(1), left:(4), right:(2), [[-2, 1, 1, 0, -2]], real: [[-2, -1, 0, 0, -2]]
i:(2), left:(2), right:(3), [[-2, 1, 1, 0, -2]]
i:(2), left:(2), right:(3), [[-2, 1, 0, 1, -2]], real: [[-2, -1, -1, 0, -2]]
i:(3), left:(0), right:(4), [[-2, 1, 0, 1, -2]]
i:(3), left:(0), right:(4), [[-3, 1, 0, 1, -1]], real: [[-3, -2, -2, -1, -2]]
i:(4), left:(0), right:(0), [[-3, 1, 0, 1, -1]]
i:(4), left:(0), right:(0), [[-3, 1, 0, 1, -1]], real: [[-3, -2, -2, -1, -2]]
注意我这里每个iteration还是把before和after都打了, 因为这题实际上是有变化的; 这样看起来感觉还是方便一些;
count subsuming intervals
所以好像是, 最后得到这个端点count之后, 从头到尾走一遍, 走到i这个位置的时候的sum, 就代表i这个位置有多少个interval; 这个好像就是一个专门用来count comprehending intervals的技巧;
这个也解释了, 为什么设计的时候, 右边端点要是一个开区间: 这样就让定义更加准确: sum of [0..i] is the number of intervals overlapping at i;
这个算法还是学到很多花招的;
回过头来看看这个最优解, 除开这个interval的技巧, 本身的题目算法上面, 还是符合了我之前的预测的, 最后解法依赖的不是一个什么高端的通用解法, 而是首先要求你对题目的理解加深, 发现一个规律, 比如对于每一个数字, 只有一个interval内的rotation, 会让他丢分; 找到这个关键规律之后, 后面的推理就还算可以接受了;
当然, 这题如果想不到这个interval技巧, 老实说也做不到O(N);
Key point
Don’t calculate the score for K=0, we don’t need it at all.
(I see almost all other solutions did)
The key point is to find out how score changes when K++Time complexity:
“A will have length at most 20000.”
I think it means you should find a O(N) solution.Explanation:
- Search the index where score changes and record the changement to a list.
- A simple for loop to calculate the score for every K value.
- Find the index of best score.
What value of K changes score?
a) get point
Each time when we rotate, we make index 0 to index N-1, then we get one more point.
b) loss point
(i - A[i] + N) % N is the value of K making A[i]'s index just equal to A[i].
For example, If A[6] = 1, then K = (6 - A[6]) % 6 = 5 making A[6] to index 1 of new array.
So when K=5, we get this point for A[6]
Then if K is bigger when K = (i - A[i] + 1) % N, we start to lose this point, making our score -= 1
All I have done is record the value of K for all A[i] where we will lose points.c) A[i]=0
Rotation makes no change for it, becasue we alwars have 0 <= index.
However, it is covered in a) and b)
public int bestRotation(int[] A) {
int N = A.length;
int change[] = new int[N];
for (int i = 0; i < N; ++i) change[(i - A[i] + 1 + N) % N] -= 1;
int max_i = 0;
for (int i = 1; i < N; ++i) {
change[i] += change[i - 1] + 1;
max_i = change[i] > change[max_i] ? i : max_i;
}
return max_i;
}
没怎么看懂, 为什么这里只要计算一个端点, 以及为什么第二个循环里面要+1;
Very brilliant solution! It takes me quite a while to understand.
Here is my understanding in detail:
For one step move left, we can figure out how points change with respect to the last position.
For each element, it must satisfy one of the three cases when moving from position i to position (i - 1 + N) % N:
- No point get and no point lose, this happens when A[i] > i;
- One point get, this happens when it moves from 0 to N - 1;
- One point lost, this happens when A[i] == i and moves to i - 1.
首先他这里就有一个讲的不对, 加分的还有一种情况, 就是从A[i] == i的右边过来的时候, 也是加分的;
change[k] actually records all the lost points after k steps moving left, by calculating how many elements would lose point at k.
The relationship of turning point k and initial position of element i is: k = (i - A[i] + 1 + N) % N.
So by looping i, we can calculate the vector of change[k].
The second for loop actually calculate total changes in k step moving left via k - 1, so you could think of
totalChange[k] = totalChange[k - 1] + change[k] + 1, as an equivalent as change[k] += change[k - 1] + 1.
The above applies well when 0 < A[i] < A.length, but what if A[i] = 0 or A[i] = A.length()?
Their turning point k = (i - 0(or N) + 1 + N) % N = i + 1 is not real, because they never lose point! (0 always counts one point, and N never).
However, assume that 0(or N) is at position i in original array, and it needs i steps to move to position 0.
So when it arrives at the turning point i + 1, it is actually moving from 0 to A.length - 1,
which means we simultaneously subtract 1(in change[k]) and add 1 for totalChange[k].
Hope this could help.
感觉这个解释还是有点毛病的, 看这个trace:
Your input
[2,3,1,4,0]
Your stdout
i:(0): [[0, 0, 0, 0, -1]]
i:(1): [[0, 0, 0, 0, -2]]
i:(2): [[0, 0, -1, 0, -2]]
i:(3): [[-1, 0, -1, 0, -2]]
i:(4): [[-2, 0, -1, 0, -2]]
[[-2, -1, -1, 0, -1]]
就拿2来说, 你看, 他这里是根本不记录加分的; 那你的意思是只记录减分? 好像是, 比如i=0的时候, 对于2, 只有shift 4的时候, 减分了, 这个是符合图上的说明的;
他这个思路还是清晰的, 第一个循环, 是针对每一个数字, 考虑shift by k对这个数字的影响, 然后k = 0..N-1, 全都考虑到; 然后有了这个信息之后(实际上只记录了减分影响), 我们下一个循环就要着手寻找最好的k了; 因为题目给的这个数组, 实际上只是一个permutation, 所以最后无论你选择的最好的k是多少, 最后所有的数字都是一起移动; 所以这个时候你就遍历所有的k, 然后把所有的数字承受的减分计算起来就行, 看看哪个k最好;
但是这个人的解释实际上还是很虚的, 有几个关键的地方还是没有解释:
- 为什么只记录减分就行了? 这个也是这个解法跟awice的解法最大的不同;
- 第二个循环为什么要+1? 我试了一下, 没有这个+1, 就错了;
- 第二个循环这个最好, 是怎么定义的? 注意看这个OP选的并不是一个找最值的过程, 而是看有没有那个change[k]能带来total的正增长, 这个对应的是什么逻辑?
这些都是真正标志这个算法的个性的东西, 都没有解释;
事实上, 如果每一个change[k]...不对, 我上面的说法有问题, change[k]实际上记录的是对于一个k, 整个A失去的分数; 这也是为什么计算的时候是一个类似count一样的++的过程; 每一个[k]实际上考虑了所有的A的元素带来的影响;
然后第二步就可以选择带来减分最少的一个k就行了;
原来的OP还有其他的语言的解法:
class Solution(object):
def bestRotation(self, A):
N = len(A)
change = [1] * N
for i in range(N): change[(i - A[i] + 1) % N] -= 1
for i in range(1, N): change[i] += change[i - 1]
return change.index(max(change))
这个看起来就比较正常, 但是这里还是一个很奇怪的地方, 比如你看他的change的初始值是所有的都是1, 然后最后返回的是total最大的那个index; 我把这个初始值改成0, 就不对了;
这两个语言的算法感觉实际上背后应该还是有一个什么没有被注意到的地方, 导致可以用这样的差别的算法来写的;
真的看不懂, 回头再来看;
Thanks for sharing, but I do find this solution still confusing as compared to the editorial. They look alike, but the differences are hard for me to resolve.
- Why does the python solution and the java solution not look alike?
- in the java solution's 2nd pass: Why do you have to do the
+1,and why do you return theI checked, theithat causes a positive increment to the total?+1is not optional.- in the python version, why do you have to initialize everything of
changeto 1? I checked, 0 does not work.- you return the index of max in the python version, so is this still the same logic used in the java version? How do they unify?
- This is regarding the editorial solution: in that solution, we actually consider not only losing points, but also gaining points. Why is gaining points not necessary to consider in your solution? When you try
k=0..N-1, it is possible the total be improving over some iteration ofk.Thanks for checking all my solutions. Not everyone does that. Here are my answers for all your questions.
Q2 As I said in “Get point”, score increase 1 point as K++ for sure. Because we rotate current element of index 0 to index N-1. That is only way that we can gain point.
Q1-2 So the change variable should be initialized as all 1s, just as what I have done in Python.
Q1-1 In java I saved one line from Arrays.fill(change, 1); and I did this part in my second loop.
Q1-3, Yes it is the same logic. I’m less familiar with Java and I don’t know a better way to return the index of max element.
这样好像说得通了, 他其实是观察到, 当我们把K完全走完(0..N-1)的情况下, 每一个数字反正只能导致一次加分, 所以就静态处理算了;
另外, 虽然是静态处理, 但是不能忽略, 因为每个数字导致加分的K是不一样的, 所以我们在比较K的时候, 仍然要保留这个看起来跟常数一样的1;
for (int i = 1; i < N; ++i) {
change[i] += change[i - 1] + 1;
max_i = change[i] > change[max_i] ? i : max_i;
}
这里其实就是找一个最大值而已, 我自己想多了, 以为找的是一个uptick;
这个+1如果还没有理解, 他这里每一步都+1的反而实际上好理解一些, 因为每次你K++的时候, 实际上比如我们这个长度为5的例子, 那么5个数字当中肯定有一个完成了0->4的转换, 然后收获加分, 至于是哪一个, 不重要, 反正是有就行了; 而且这个加分机会对于每一个数字来说其实是唯一的加分机会;
改成Python类似的写法:
class Solution {
public int bestRotation(int[] A) {
int N = A.length;
int change[] = new int[N];
Arrays.fill (change, 1);
for (int i = 0; i < N; ++i) {
change[(i - A[i] + 1 + N) % N] -= 1;
}
int max_i = 0;
for (int i = 1; i < N; ++i) {
change[i] += change[i - 1];
max_i = change[i] > change[max_i] ? i : max_i;
}
return max_i;
}
}
果然是AC的;
总的来说这个人的抽象能力还是很强的; 理解了他的描述之后回头看看, 确实就是这么一个写法; 在搜索k = 0..N-1的过程, 实际上就是类似你在一个一个的shift的过程是一样的;
class Solution {
public int bestRotation(int[] A) {
int len = A.length;
// Store scores for each K value
int[] kScores = new int[len];
for (int i = 0; i < len; i ++) {
int v = A[i];
// Ideal K is the K that puts A[i] in location i.
int idealK = (len - v + i) % len;
// Increment kScores for all possible K's s.t. v in A rotated by K will improve the score.
for (int j = 0; j < len - v; j ++) {
kScores[idealK] = kScores[idealK] + 1;
idealK --;
if (idealK < 0) idealK = len - 1;
}
}
// Get the best K
int bestK = 0;
int bestScore = -1;
for (int k = 0; k < len; k ++) {
int score = kScores[k];
if (score > bestScore) {
bestK = k;
bestScore = score;
}
}
return bestK;
}
}
这个实际上就是类似editorial, 但是没有想到interval技巧的做法, 这个做法严格来说是N^2, 因为每一个数字bad的位置实际上正好是N/2(0除外); 所以最后基本是可以稳定确定是O(N^2)的复杂度, 不过最后居然也AC了也是奇怪;
而且代码写的也很奇怪, idealK和j实际上重复了;
int bestRotation(vector<int>& A) {
int size = A.size(), score = 0;
vector<int> bad_intervals(size);
// for bad intervals for each element from the array
for(int i = 0; i < size; i++){
int num = A[i];
if(num <= i) score++;
// if A[i] element ends up between left and right index of given array, it will not score
int left = (i - num + 1 + size) % size;
int right = (i + 1) % size;
// create an interval [left, right] which is not good for A[ith] element
bad_intervals[left]--;
bad_intervals[right]++;
// if the bad interval for A[i] is wrapped around the array
// split the interval into two intervals [0, left] and [right, 10];
// we do not need to store 10th value for interval - not useful
if(left > right)
bad_intervals[0]--;
}
// after this point apply merge-intervals logic
// see leetcode questions on merging intervals
// in short, minimum overlap inerval is the answer
int k = 0, max_score = score;
for(int i = 1; i < size; i++){
score += bad_intervals[i];
if(max_score < score)
max_score = score, k = i;
}
return k;
}
看起来好像就是awice答案的原型啊; 这个人的代码确实是写的好;
这个merge intervals我好像做过了, 翻回去看了一下, 好像没有看到这种正负端点的思路?
不知道他什么意思;
submission: 7(100):
class Solution {
// Time - O(n), Space - O(n)
// (i - A[i] + N) % N is the value of K making the value of A[i] to pos A[i], then after K, we'll lose one point
// Steps
// Step 1: Search the index where score decrease and record the changement to a list changes
// Step 2: A simple loop to calculate the score for every K value
// scores[K] = score[K - 1] + change[K]
// accumulated changes so we can get the changed score for every K value compared to K=0
// Step 3: find the index of best score
public int bestRotation(int[] A) {
int n = A.length;
int[] changes = new int[n];
for (int i = 0; i < n; i++) {
changes[(i - A[i] + 1 + n) % n] -= 1;
}
int maxIndex = 0;
for (int i = 1; i < n; i++) {
changes[i] += changes[i - 1] + 1;
if (changes[i] > changes[maxIndex]) {
maxIndex = i;
}
}
return maxIndex;
}
}
就是discussion最优解; 因为只计算一个端点, 最后实际计算的时候好像是占了便宜;
uwi, 187(17). 速度倒是不怎么样;
class Solution {
public int bestRotation(int[] a) {
int n = a.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(100000, (x, y) ->
-((x[0]-x[1]) - (y[0]-y[1]))
);
for(int i = 0;i < n;i++){
pq.add(new int[]{a[i], i});
}
boolean[] less = new boolean[n];
int best = -1;
int arg = -1;
int all = n;
for(int i = 0;i < n;i++){
while(!pq.isEmpty()){
if(pq.peek()[0]-pq.peek()[1] > -i){
less[pq.poll()[1]] = true;
all--;
}else{
break;
}
}
if(all > best){
best = all;
arg = i;
}
if(less[i]){
less[i] = false;
}
all++;
pq.add(new int[]{a[i]-n, i});
}
// 0-0 2-1 3-2
// 0-3 2-4 3-2
return arg;
}
}
维护一个按照leftshift长度降序的PriorityQueue, 然后是一个什么乱七八糟的操作, 感觉他应该是理解这个题目了, 不过这个算法他想了30分钟, 还有1个bug(他们这种选手都是提交之前已经自己挖空心思想testcase了, 提交了还有的bug肯定是非常没有意料到的), 说明这个算法还是有点adhoc的成分在里面的; 大概看看, 暂时没有时间深挖了; 不过感觉这题的中心思想他也理解了, 就是找这个left shift, 这个是一个关键的值. 后续的处理, 好像是各人有各人的做法了;
flow写的比较奇怪, 暂时是真的没有时间去看了;
Problem Description
Given an array A, we may rotate it by a non-negative integer K so that the array becomes A[K], A[K+1], A{K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1]. Afterward, any entries that are less than or equal to their index are worth 1 point.
For example, if we have [2, 4, 1, 3, 0], and we rotate by K = 2, it becomes [1, 3, 0, 2, 4]. This is worth 3 points because 1 > 0 [no points], 3 > 1 [no points], 0 <= 2 [one point], 2 <= 3 [one point], 4 <= 4 [one point].
Over all possible rotations, return the rotation index K that corresponds to the highest score we could receive. If there are multiple answers, return the smallest such index K.
Example 1:
Input: [2, 3, 1, 4, 0]
Output: 3
Explanation:
Scores for each K are listed below:
K = 0, A = [2,3,1,4,0], score 2
K = 1, A = [3,1,4,0,2], score 3
K = 2, A = [1,4,0,2,3], score 3
K = 3, A = [4,0,2,3,1], score 4
K = 4, A = [0,2,3,1,4], score 3
So we should choose K = 3, which has the highest score.
Example 2:
Input: [1, 3, 0, 2, 4]
Output: 0
Explanation: A will always have 3 points no matter how it shifts.
So we will choose the smallest K, which is 0.
Note:
- A will have length at most 20000.
- A[i] will be in the range [0, A.length].
Difficulty:Hard
Total Accepted:737
Total Submissions:3K
Contributor:ngoc_lam