문제 Problem
Status: Solved Difficulty: Easy Topics: Array
Hint Given an array nums, return true if the array was originally sorted in non-decreasing order, then rotated some number of positions (including zero). Otherwise, return false.
There may be duplicates in the original array.
Note: An array A rotated by x positions results in an array B of the same length such that B[i] == A[(i+x) % A.length] for every valid index i.
Example 1:
Input: nums = [3,4,5,1,2] Output: true Explanation: [1,2,3,4,5] is the original sorted array. You can rotate the array by x = 3 positions to begin on the element of value 3: [3,4,5,1,2].
Example 2:
Input: nums = [2,1,3,4] Output: false Explanation: There is no sorted array once rotated that can make nums.
Example 3:
Input: nums = [1,2,3] Output: true Explanation: [1,2,3] is the original sorted array. You can rotate the array by x = 0 positions (i.e. no rotation) to make nums.
제출 Submission
add만 있는 간단 singly circular linked list 구현
class Node {
int data;
Node next;
Node(int data){
this.data = data;
this.next = null;
}
}
class CircularLinkedList {
Node head;
Node tail;
void add(int data){
Node node = new Node(data);
if(this.head == null){
this.head = node;
this.tail = node;
this.tail.next = head;
} else {
this.tail.next = node;
this.tail = node;
tail.next = head;
}
}
}
class Solution {
public boolean check(int[] nums) {
int l = nums.length;
CircularLinkedList cll1 = new CircularLinkedList();
CircularLinkedList cll2 = new CircularLinkedList();
for (int n : nums) // nums의 값들을 cll1에 넣어주기
cll1.add(n);
Arrays.sort(nums); // 정렬 후 정렬된 nums의 값들을 cll2에 넣어주기
for (int n : nums)
cll2.add(n);
Node startNode = cll1.head;
for (int i = 0; i < l; i++) {
Node curr1 = startNode;
Node curr2 = cll2.head;
boolean match = true;
do {
if (curr1.data != curr2.data) { 첫 노드가 다르면 match되지 않기에 종료. 같으면 계속 비교
match = false;
break;
}
curr1 = curr1.next;
curr2 = curr2.next;
} while (curr1 != startNode);
if (match) return true; // 결과적으로 같으면
startNode = startNode.next; // match되지 않았으면 next 노드로 다시 비교
}
return false;
}
}
Editorial
n번씩 다 돌려보고 배열 생성하고 비교 -> O(N^2) class Solution {
public boolean check(int[] nums) {
int n = nums.length;
// Construct the rotated array
int[] checkSorted = new int[n];
// Iterate through all possible rotation offsets
for (int rotationOffset = 0; rotationOffset < n; ++rotationOffset) {
int currIndex = 0;
for (int index = rotationOffset; index < n; ++index) {
checkSorted[currIndex++] = nums[index];
}
for (int index = 0; index < rotationOffset; ++index) {
checkSorted[currIndex++] = nums[index];
}
// Check if the constructed array is sorted
boolean isSorted = true;
for (int index = 0; index < n - 1; ++index) {
if (checkSorted[index] > checkSorted[index + 1]) {
isSorted = false;
break;
}
}
}
}
}
https://leetcode.com/problems/check-if-array-is-sorted-and-rotated/editorial
Other Solution
모듈로로 index를 circular하게 활용. 인접한 수끼리 비교해서 왼쪽이 큰 경우가 2번 이상이면 false. (최댓값 다음 최솟값이 인접한 한 번만 허용) -> O(N) class Solution { public boolean check(int[] nums) { int count = 0, n = nums.length;
for (int i = 0; i < n; i++) {
if (nums[i] > nums[(i + 1) % n])
count++;
if (count > 1)
return false;
return true;
}
}
}
GitHub Comments