배열이 단조로운 지 확인하십시오. 즉, 단조 증가 또는 단조 감소

Aug 20 2020

배열 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));
}

}

답변

7 AJNeufeld Aug 20 2020 at 04:49

공전

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;
        }
    }
5 AliceRyhl Aug 20 2020 at 19:52

루프는 다소 복잡합니다. 가능한 경우 더 간단한 논리를 사용하는 것이 일반적으로 루프를 추론하기 더 간단하게 만들기 때문입니다. 예를 들어 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이고 증가 또는 감소 여부에 따라 양수 또는 음수입니다.

lastCmp0 일 때 , 우리는 아직 증가 또는 감소를 보지 못했습니다. 즉, 모든 정수가 동일합니다. 경우 lastCmp제로가 아닌, 우리는 증가 또는 감소 하나를 보았다. 시퀀스가 단조롭지 않으면 결국 첫 번째 변화와 반대 방향으로 이동 한 쌍에 도달하게되는데, 이는 두 번째 조건이 감지 할 것입니다.

목록이 두 요소보다 짧으면 루프가 전혀 실행되지 않고 true를 반환합니다.

4 superbrain Aug 21 2020 at 00:03
  • 즉시 결정하면 더 나은 성능과 단순성을 얻을 수 있습니다. 첫 번째 값과 마지막 값을 비교하면 증가 / 감소 / 상수 중 어느 것을 확인해야하는지 즉시 알 수 있습니다 .

  • 당신이해야 할 일은 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:]))
3 RoToRa Aug 20 2020 at 15:16

나는 단조 로움의 증가와 감소를 무차별 적으로 확인하는 단일 모 놀리 식 기능을 갖는 것을 좋아하지 않습니다. 대부분의 실제 시나리오에서 나는 그것이 증가하는지 감소하는지 알아야 할 필요가 있다고 생각합니다.

이를 기반으로 구체적으로 정의합니다.

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에서는 코드가 더 잘 구조화되고 더 읽기 쉽고 재사용이 가능합니다.

tevemadar Aug 20 2020 at 22:50

@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(:)변형이하는 일). 또한 단락 returns 때문에 루프가 완료되면 배열이 단조롭다는 것을 의미합니다. 또한 numbers.length-1루프 상태 에있는 위험에 대한 설명 도 적용되었습니다.