英文:
How to check if an array is sorted and rotated clockwise in if it is in decreasing order in Java?
问题
I will translate the provided text into Chinese for you:
我需要检查数组是否按递减顺序排列并进行了旋转,例如:44 43 11 10 9
按递减顺序排列,当我们旋转两次后,它将变成 10 9 44 43 11
。
我已经附上了我的代码,但对于 [43 44 11 10 9]
这种情况,它不够优化,因为在这种情况下,数组未经排序和旋转,因为当我们对数组进行排序时,它将变成 44 43 11 10 9,并且从旋转的角度来看不可能变成 43 44 11 10 9,实际上输出应该是 "No",但在我的代码中输出是 "Yes"。根据我的代码,我无法处理优化我的代码的给定情况。
我试图实现的情况是,如果数组按递减顺序排列并按顺时针方向旋转。
例如:6 5 4 3 2 1
是按递减顺序排列的数组,但当我们旋转两次后,它将变成 2 1 6 5 4 3
,输出应该是 "Yes"。
但对于 44 43 11 10 9
,数组按递减顺序排列,但在 (43 44 11 10 9)
这种情况下未经旋转,因此输出应该是 "No"。
英文:
I have to check whether the array is in decreasing order and rotated,
for example: 44 43 11 10 9
is sorted in decreasing order and when we rotate it twice then it will be 10 9 44 43 11
.
I have attached my code but it is not optimal for case of [43 44 11 10 9]
because in this case the array is not sorted and rotated, because when we sort the array it will be 44 43 11 10 9 and there is no possibilities in terms of rotation that it would be 43 44 11 10 9 , In fact the output should be "No" but in my case output is "Yes". As per my code, I am unable to handle the given case for optimize my code.
class Main {
public static boolean antiClockRotation(int arr[]) {
int max = Integer.MIN_VALUE;
int index = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
index = i;
}
}
if (index == 0) {
return false;
}
int i = 0;
int j = 1;
while (i < index && j < index) {
if (arr[i] <= arr[j]) {
return false;
}
i++;
j++;
}
int k = index;
int l = index+1;
while (k < arr.length - 1 && l < arr.length) {
if (arr[k] <= arr[l]) {
return false;
}
k++;
l++;
}
return true;
}
public static void main(String[] args) {
// Your code here
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for (int i = 0; i < n; i++) {
int size = sc.nextInt();
int arr[] = new int[size];
for (int j = 0; j < size; j++) {
arr[j] = sc.nextInt();
}
if (antiClockRotation(arr)) {
System.out.println("Yes");
}
else{
System.out.println("No");
}
}
}
}
I am trying to achieve the case if the array is sorted and rotated clockwise in decreasing order.
For example : 6 5 4 3 2 1
is the array which is in decreasing order but when we rotate 2 times so it will be 2 1 6 5 4 3
and output should be "Yes".
But in case of 44 43 11 10 9
the array is in decreasing order but in the case of
(43 44 11 10 9)
it is not rotated so the output should be "No".
答案1
得分: 1
所有你需要做的是跟踪拐点左侧的最高元素。例如,44、43、11、10、9,每个元素都比它左侧的元素小,所以答案是是,但是43、44、11、10、9,你会发现44大于43(或者通常是左侧最大的元素)。在拐点之后,每个元素都必须比它左侧的元素小,而最后一个元素(9)必须大于拐点左侧最大的元素(43),所以答案是不。
编辑:
添加的代码。
public static boolean isSortedAndRotated(int arr[]) {
int n = arr.length;
if (n <= 1) {
return true;
}
int fst = Integer.MIN_VALUE;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
if (fst > Integer.MIN_VALUE) {
return false;
}
fst = arr[0];
}
}
return arr[n - 1] >= fst;
}
英文:
All you need to do is track the highest element to the left of the inflection point. For example, 44, 43, 11, 10, 9, every element is smaller that the one on its left, so, answer is yes, but 43, 44, 11, 10, 9, you find 44 greater than 43 (or whatever in general is the greatest on the left). After the inflection point, every element must be smaller than the one on its left, and the last element (9) must be greater than the greatest element on the left of the inflection point (43), so, the answer is no.
Edit:
Added code.
public static boolean isSortedAndRotated(int arr[]) {
int n = arr.length;
if (n <= 1) {
return true;
}
int fst = Integer.MIN_VALUE;
for (int i = 1; i < n; i++) {
if (arr[i] > arr[i - 1]) {
if (fst > Integer.MIN_VALUE) {
return false;
}
fst = arr[0];
}
}
return arr[n - 1] >= fst;
}
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库,让每个人都能够通过互相帮助和分享经验来进步。
评论