https://leetcode.com/problems/smallest-rotation-with-highest-score/
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:
Awill have length at most20000.A[i]will be in the range[0, A.length].
Don't calculate the score for
(I see almost all other solutions did)
The key point is to find out how score changes when
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.
“A will have length at most 20000.”
I think it means you should find a O(N) solution.
How dosen score change when K++ ?
- Get point
Each time when we rotate, we make index0to indexN-1, then we get one more point.
We know that for sure, so I don't need to record it. - Lose point
(i - A[i] + N) % Nis the value of K makingA[i]'sindex just equal toA[i].
For example, IfA[6] = 1, thenK = (6 - A[6]) % 6 = 5makingA[6]toindex 1of new array.
So whenK=5, we get this point forA[6]
Then ifKis bigger whenK = (i - A[i] + 1) % N, we start to lose this point, making our score -= 1
All I have done is record the value ofKfor allA[i]where we will lose points. A[i]=0
Rotation makes no change for it, becasue we alwars have0 <= index.
However, it is covered in "get point" and "lose point".
Explanation of codes
- Search the index where score decrease and record this changement to a list
change. - A simple for loop to calculate the score for every
Kvalue.score[K] = score[K-1] + change[K]
In my codes I accumulatedchangesso I get the changed score for everyKvalue compared toK=0 - Find the index of best score.
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;
}
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, 2wraps 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.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; }https://leetcode.com/problems/smallest-rotation-with-highest-score/discuss/118839/Simple-Java-O(n)-Solution
The trick of this problem is to convert it into finding most overlap interval problem (like meeting room II, finding most airplanes at a time)
public int bestRotation(int[] A) {
int n = A.length;
int[] a = new int[n]; // to record interval start/end
for (int i = 0; i < A.length; i++) {
a[(i + 1) % n]++; // interval start
a[(i + 1 - A[i] + n) % n]--; // interval end
}
int count = 0;
int maxCount = -1;
int res = 0;
for (int i = 0; i < n; i++) { // find most overlap interval
count += a[i];
if (count > maxCount) {
res = i;
maxCount = count;
}
}
return res;
}
Let's go through an example first. If the input is{2,4,1,3,0}, We write down all status when rotate k steps.
Number:::::: 2 4 1 3 0
k = 0 index: 0 1 2 3 4
k = 1 index: 4 0 1 2 3
k = 2 index: 3 4 0 1 2
k = 3 index: 2 3 4 0 1
k = 4 index: 1 2 3 4 0
Number:::::: 2 4 1 3 0
k = 0 index: 0 1 2 3 4
k = 1 index: 4 0 1 2 3
k = 2 index: 3 4 0 1 2
k = 3 index: 2 3 4 0 1
k = 4 index: 1 2 3 4 0
If we look in each column, then index for one particular number is somehow decrease with a valley(0). We want to know in which K steps the index is greate or equal than the corresponding number. For number 2, k should be{1,2,3}, for number 1, k should be{0,1,3,4}.
So our task is to collect all k rows in which the index >= number for each paritular number.
So our task is to collect all k rows in which the index >= number for each paritular number.
- If number > index in original array:
As index is decreasing, so we need to find in which row the index is equals to (length - 1), the largest index of array. Then go down until index == number. - If number <= index in original array:
k = 0 is always valid, and 0 through the row in which index == number is the last valid row. Also, don't forget the index == len - 1 this corner case;
There are some math tricks from maybe high school: largest index row = (index + 1) % len; Row in which index == number = (index + len - num) % len;
We just need to update count[min] and count[max] to avoid O(n) time to record our result.
We just need to update count[min] and count[max] to avoid O(n) time to record our result.
public int bestRotation(int[] A) {
int[] count = new int[A.length + 1];
int len = A.length;
for(int index = 0; index < A.length; index ++){
int num = A[index];
if(index < num){
int maxLenK = (index + 1) % len;
int ori = (index + len - num) % len;
count[maxLenK] ++;
count[ori + 1] --;
}else{ // index >= num
int ori = (index + len - num) % len;
count[0] ++;
count[ori + 1] --;
if(index != len - 1){
count[(index + 1) % len] ++;
count[len] --;
}
}
}
int max = count[0];
int res = 0;
for(int i = 1; i < len; i ++){
count[i] = count[i] + count[i - 1];
if(count[i] > max){
max = count[i];
res = i;
}
}
return res;
}(区间标记)
- 对于每个数字，求出其能得分的轮调区间。比如样例 1 中下标为
1位置的数字3，其能得分的轮调区间为[2, 3]。再比如下标为2的数字1，其能得分的区间有两段，分别为[0, 1]和[3, 4]。 - 具体地，每个数字最多有两段能得分的区间。假设数组长度为
n，对于在下标为i位置的数字A[i]，如果A[i] >= n，则得分区间不存在；在A[i] < n的情况下，如果A[i] > i，则得分区间为[i + 1, i + n - A[i]]；如果A[i] < i，则得分区间为[0, i - A[i]]和[i + 1, n - 1]。 - 得到了每个数的合法区间，我们通过区间标记的方法求出得分最大的点。如果
[l, r]是一个得分区间，则我们标记valid[l]++且valid[r + 1]--，然后求出valid数组的前缀和。数组中最大值的点就是得分最大的点。
https://www.acwing.com/solution/LeetCode/content/2552/
给定一个数组
A，我们可以将它按一个非负整数 K 进行轮调，这样可以使数组变为 A[K], A[K+1], A[K+2], ... A[A.length - 1], A[0], A[1], ..., A[K-1] 的形式。此后，任何值小于或等于其索引的项都可以记作 1 分。
例如，如果数组为
[2, 4, 1, 3, 0]，我们按 K = 2 进行轮调后，它将变成 [1, 3, 0, 2, 4]。这将记作 3 分，因为 1 > 0 [没有得分], 3 > 1 [没有得分], 0 <= 2 [1 分], 2 <= 3 [1 分], 4 <= 4 [1 分]。
在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调索引 K。如果有多个答案，返回满足条件的最小的索引 K。
样例
输入：[2, 3, 1, 4, 0]
输出：3
解释：
下面列出了每个 K 的得分：
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
所以我们应当选择 K = 3，得分最高。
输入：[1, 3, 0, 2, 4]
输出：0
解释：
无论怎么变化总是有 3 分。
所以我们将选择最小的 ，即 0。
