배열이 단조로운 지 확인하십시오. 즉, 단조 증가 또는 단조 감소
배열 A는 모든 i <= j, A [i] <= A [j]에 대해 모노톤 증가입니다. 배열 A는 모든 i <= j, A [i]> = A [j] 인 경우 감소하는 단조입니다.
주어진 배열 A가 단조로운 경우에만 true를 반환합니다.
public class MonotonicArray {
public boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
if (numbers.length == 1) {
return true;
}
boolean increasing = false;
boolean decreasing = false;
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
if (numbers[index + 1] > numbers[index]) {
if (!decreasing) {
increasing = true;
} else {
return false;
}
}
else {
if (!increasing) {
decreasing = true;
} else {
return false;
}
}
}
return increasing || decreasing;
}
}
테스트 사례 :
class MonotonicArrayTest extends MonotonicArray {
@org.junit.jupiter.api.Test
void isMonotonic1() {
int[] array = new int[]{1,2,3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic2() {
int[] array = new int[]{-1,-2,-3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic3() {
int[] array = new int[]{1,2,1};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic4() {
int[] array = new int[]{-1,2,-9};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic5() {
int[] array = new int[]{9,3,2};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic6() {
int[] array = new int[]{};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic7() {
int[] array = new int[]{1};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic8() {
int[] array = new int[]{9,7,5,4,8,10};
assertEquals(false,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic9() {
int[] array = new int[]{1,1,2,3};
assertEquals(true,IsMonotonic(array));
}
@org.junit.jupiter.api.Test
void isMonotonic10() {
int[] array = new int[]{1,1,0,-1};
assertEquals(true,IsMonotonic(array));
}
}
답변
공전
IsMonotonic(...)
작동하는 데 MonotonicArray
클래스 의 인스턴스가 필요하지 않으므로 정적이어야합니다.
일관성
길이 1의 배열을 단조롭게 특수한 경우입니다. 진짜야? 증가하거나 감소하지 않습니다.
어때 IsMonotonic(new int[]{1, 1, 1, 1})
? 해야 그 날 것으로 보인다 true
,하지만 돌아갑니다 false
. 확실히 테스트 케이스로 추가해야합니다. 그리고 그것이 반환되어야 true
한다면 ...
최적화
... 길이 1을 확인하는 것은 너무 제한적입니다. 길이 2 배열도 항상 단조롭습니다. 혹시:
if (numbers.length == 1) {
return true;
}
해야한다:
if (numbers.length <= 2) {
return true;
}
루핑
이건 못 생겼어. Java는 numbers.length - 1
계산을 상수로 최적화 합니까?
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
...
Java의 향상된 for
루프를 사용하여 숫자를 추출하고, 첫 번째 요소를 동일하게 처리 할 수 있도록 단조로운 동작에 의존하는 것이 더 나을 수 있습니다 .
int current = numbers[0];
for(int value : numbers) {
if (value != current) {
if (value < current) {
...
} else {
...
}
current = value;
}
}
루프는 다소 복잡합니다. 가능한 경우 더 간단한 논리를 사용하는 것이 일반적으로 루프를 추론하기 더 간단하게 만들기 때문입니다. 예를 들어 Integer.compare
루프에서 많은 논리를 제거하는 데 사용할 수 있습니다 .
public static boolean IsMonotonic(int[] numbers) {
int lastCmp = 0;
for (int i = 1; i < numbers.length; i++) {
int cmp = Integer.compare(numbers[i], numbers[i - 1]);
if (lastCmp == 0) {
lastCmp = cmp;
} else if (cmp != 0 && ((cmp > 0) != (lastCmp > 0))) {
return false;
}
}
return true;
}
각 반복에서 cmp
두 숫자가 같으면 변수는 0이고 증가 또는 감소 여부에 따라 양수 또는 음수입니다.
lastCmp
0 일 때 , 우리는 아직 증가 또는 감소를 보지 못했습니다. 즉, 모든 정수가 동일합니다. 경우 lastCmp
제로가 아닌, 우리는 증가 또는 감소 하나를 보았다. 시퀀스가 단조롭지 않으면 결국 첫 번째 변화와 반대 방향으로 이동 한 쌍에 도달하게되는데, 이는 두 번째 조건이 감지 할 것입니다.
목록이 두 요소보다 짧으면 루프가 전혀 실행되지 않고 true를 반환합니다.
즉시 결정하면 더 나은 성능과 단순성을 얻을 수 있습니다. 첫 번째 값과 마지막 값을 비교하면 증가 / 감소 / 상수 중 어느 것을 확인해야하는지 즉시 알 수 있습니다 .
당신이해야 할 일은
null
계약 에 따라 다릅니다. 이 문제는 LeetCode에 있습니다 . 여기서 배열에 적어도 하나의 요소가있을 것이라는 보장도 있으므로 여기에서 덮null
거나 비어있는 배열이 필요하지 않습니다 . 당신은 반환 (?) "선택"false
,하지만 당신은 단지뿐만 아니라에 대한 주장 할 수 있습니다true
"어떤 배열이"정답이 BTW되는 "아니오 요소", 오히려 비슷한 것 같다 없기 때문에true
,하지false
.
다음은 first-vs-last 검사를 사용하고 ( "증가"에 "constant"를 포함했지만) 호출자에게 합리적인 입력 (즉, 아님 null
) 을 제공해야하는 부담을줍니다 . 아무 것도 잘못한 척 조용히하는 것보다 사용자에게 오류가 발생하도록하는 것이 낫다고 생각합니다.
public boolean isMonotonic(int[] numbers) {
int last = numbers.length - 1;
if (last >= 0 && numbers[0] <= numbers[last]) {
for (int i = 0; i < last; i++) {
if (numbers[i] > numbers[i+1]) {
return false;
}
}
} else {
for (int i = 0; i < last; i++) {
if (numbers[i] < numbers[i+1]) {
return false;
}
}
}
return true;
}
BiPredicate
버전에서 영감을 RoToRa의 대답 . 이것은 BiPredicate
코드 중복을 피하기 때문에 세 가지 경우를 모두 구별합니다 .
public boolean isMonotonic(int[] numbers) {
int n = numbers.length;
if (n <= 2) {
return true;
}
BiPredicate<Integer, Integer> fail =
numbers[0] < numbers[n-1] ? (a, b) -> a > b :
numbers[0] > numbers[n-1] ? (a, b) -> a < b :
(a, b) -> a != b;
for (int i = 1; i < n; i++)
if (fail.test(numbers[i-1], numbers[i]))
return false;
return true;
}
재미를위한 파이썬 버전 :-)
from operator import eq, le, ge
def isMonotonic(numbers):
first, last = numbers[:1], numbers[-1:]
check = eq if first == last else le if first < last else ge
return all(map(check, numbers, numbers[1:]))
나는 단조 로움의 증가와 감소를 무차별 적으로 확인하는 단일 모 놀리 식 기능을 갖는 것을 좋아하지 않습니다. 대부분의 실제 시나리오에서 나는 그것이 증가하는지 감소하는지 알아야 할 필요가 있다고 생각합니다.
이를 기반으로 구체적으로 정의합니다.
public static boolean isMonotonic(int[] numbers) {
return isMonotonicIncreasing(numbers) || isMonotonicDecreasing(numbers);
}
public static boolean isMonotonicIncreasing(int[] numbers) {
return isXXX(numbers, (a, b) -> a <= b); // Not sure how to call this method
}
물론 두 번의 중복 검사가 있지만 결국 IMO에서는 코드가 더 잘 구조화되고 더 읽기 쉽고 재사용이 가능합니다.
@AJNeufeld 의 일관성 설명 을 수락하고 ( [1]
단조 적이 라는 것은 [1,1,1]
오히려 단조적일 수도 있음을 나타냄 ) 단조 적이라는 다른 설명 [x,y]
을 다시 넣으면 true
기본적으로 -s를 사용하고 배열이 그렇지 않은 경우 인식하는 것이 더 쉬울 수 있습니다. 단조로운 :
public static boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
boolean inc_or_const = true;
boolean dec_or_const = true;
int prev = numbers[0];
for (int curr : numbers) {
if (curr < prev) {
inc_or_const = false;
} else if (curr > prev) {
dec_or_const = false;
}
prev = curr;
}
return inc_or_const || dec_or_const;
}
물론 단락없이 깔끔하게 보이지만 그 후에는 원래 코드와 매우 유사한 구조를 다시 갖게됩니다.
public static boolean IsMonotonic(int[] numbers) {
if (numbers == null || numbers.length == 0) {
return false;
}
boolean inc_or_const = true;
boolean dec_or_const = true;
int prev = numbers[0];
for (int i = 1; i < numbers.length; i++) {
int curr = numbers[i];
if (curr < prev) {
inc_or_const = false;
if (!dec_or_const) {
return false;
}
} else if (curr > prev) {
dec_or_const = false;
if (!inc_or_const) {
return false;
}
}
prev = curr;
}
return true;
}
여기서는 첫 번째 요소를 자신과 비교하는 것에 대한 싫어함을 기반으로 색인화 된 액세스로 돌아갔습니다 ( for(:)
변형이하는 일). 또한 단락 return
s 때문에 루프가 완료되면 배열이 단조롭다는 것을 의미합니다. 또한 numbers.length-1
루프 상태 에있는 위험에 대한 설명 도 적용되었습니다.