ตรวจสอบว่าอาร์เรย์เป็นโมโนโทนิกหรือไม่เช่นโมโนโทนเพิ่มขึ้นหรือโมโนโทนลด

Aug 20 2020

อาร์เรย์ A โมโนโทนจะเพิ่มขึ้นหากสำหรับ i <= j, A [i] <= A [j] ทั้งหมด อาร์เรย์ A โมโนโทนจะลดลงหากสำหรับ i <= j, A [i]> = A [j] ทั้งหมด

คืนค่าจริงถ้าอาร์เรย์ A ที่ระบุเป็นโมโนโทนิกเท่านั้น

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;
        }
        ...

อาจจะดีกว่าถ้าใช้forลูปที่ปรับปรุงแล้วของ Java เพื่อแยกตัวเลขและอาศัยพฤติกรรมเชิงเดี่ยวที่ให้ความเท่าเทียมกันในการจัดการองค์ประกอบแรก:

    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ตัวแปรจะเป็นศูนย์หากตัวเลขทั้งสองเท่ากันและจะเป็นบวกหรือลบขึ้นอยู่กับว่ามีการเพิ่มขึ้นหรือลดลง

เมื่อlastCmpเป็นศูนย์เรายังไม่เห็นการเพิ่มขึ้นหรือลดลงนั่นคือจำนวนเต็มทั้งหมดมีค่าเท่ากัน ถ้าlastCmpไม่ใช่ศูนย์เราจะเห็นว่าเพิ่มขึ้นหรือลดลง หากลำดับไม่ใช่แบบโมโนโทนิกในที่สุดเราก็จะไปถึงคู่ที่เคลื่อนที่ไปในทิศทางตรงกันข้ามจากการเปลี่ยนแปลงครั้งแรกซึ่งเป็นสิ่งที่เงื่อนไขที่สองจะตรวจพบ

หากรายการสั้นกว่าสององค์ประกอบลูปจะไม่ทำงานเลยและส่งกลับค่าจริง

4 superbrain Aug 21 2020 at 00:03
  • คุณอาจได้รับประสิทธิภาพและความเรียบง่ายที่ดีขึ้นหากคุณตัดสินใจได้ทันที: การเปรียบเทียบค่าแรกกับค่าสุดท้ายจะบอกได้ทันทีว่าค่าใดที่คุณควรตรวจสอบเพิ่มขึ้น / ลดลง / คงที่

  • สิ่งที่คุณควรทำnullขึ้นอยู่กับสัญญา ปัญหานี้เกิดขึ้นกับ LeetCodeซึ่งคุณรับประกันได้ว่าอาร์เรย์จะมีองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบดังนั้นคุณไม่จำเป็นต้องครอบคลุมnullหรืออาร์เรย์ว่างเปล่า คุณ "เลือก" (?) ที่จะกลับมาfalseแต่คุณสามารถเพียงเช่นกันเถียงtrueตั้งแต่ "อาเรย์ไม่" ดูเหมือนว่าค่อนข้างคล้ายกับ "ไม่มีองค์ประกอบ" ซึ่งคำตอบที่ถูกต้องคือ BTW ไม่truefalse

นี่คือสิ่งที่ใช้การตรวจสอบครั้งแรกเทียบกับครั้งสุดท้าย (แม้ว่าฉันจะรวม "ค่าคงที่" ไว้ใน "การเพิ่มขึ้น") และทำให้ผู้โทรเป็นภาระในการป้อนข้อมูลที่สมเหตุสมผล (เช่นไม่ใช่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;
    }

เวอร์ชัน Python เพื่อความสนุก :-)

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(:)ตัวแปรทำ) โปรดทราบว่าที่นี่เนื่องจากการลัดวงจรการreturnสิ้นสุดของลูปหมายความว่าอาร์เรย์เป็นโมโนโทนิกอย่างแน่นอน นอกจากนี้ยังมีการใช้ข้อสังเกตเกี่ยวกับอันตรายของการมีnumbers.length-1เงื่อนไขการวนซ้ำด้วย