ตรวจสอบว่าอาร์เรย์เป็นโมโนโทนิกหรือไม่เช่นโมโนโทนเพิ่มขึ้นหรือโมโนโทนลด
อาร์เรย์ 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));
}
}
คำตอบ
คงที่
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;
}
}
ลูปค่อนข้างซับซ้อน โดยทั่วไปแล้วการใช้ตรรกะที่ง่ายกว่านี้จะดีกว่าถ้าเป็นไปได้เนื่องจากจะทำให้การวนซ้ำง่ายขึ้นในการให้เหตุผล ตัวอย่างเช่นคุณสามารถใช้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
ไม่ใช่ศูนย์เราจะเห็นว่าเพิ่มขึ้นหรือลดลง หากลำดับไม่ใช่แบบโมโนโทนิกในที่สุดเราก็จะไปถึงคู่ที่เคลื่อนที่ไปในทิศทางตรงกันข้ามจากการเปลี่ยนแปลงครั้งแรกซึ่งเป็นสิ่งที่เงื่อนไขที่สองจะตรวจพบ
หากรายการสั้นกว่าสององค์ประกอบลูปจะไม่ทำงานเลยและส่งกลับค่าจริง
คุณอาจได้รับประสิทธิภาพและความเรียบง่ายที่ดีขึ้นหากคุณตัดสินใจได้ทันที: การเปรียบเทียบค่าแรกกับค่าสุดท้ายจะบอกได้ทันทีว่าค่าใดที่คุณควรตรวจสอบเพิ่มขึ้น / ลดลง / คงที่
สิ่งที่คุณควรทำ
null
ขึ้นอยู่กับสัญญา ปัญหานี้เกิดขึ้นกับ LeetCodeซึ่งคุณรับประกันได้ว่าอาร์เรย์จะมีองค์ประกอบอย่างน้อยหนึ่งองค์ประกอบดังนั้นคุณไม่จำเป็นต้องครอบคลุมnull
หรืออาร์เรย์ว่างเปล่า คุณ "เลือก" (?) ที่จะกลับมาfalse
แต่คุณสามารถเพียงเช่นกันเถียงtrue
ตั้งแต่ "อาเรย์ไม่" ดูเหมือนว่าค่อนข้างคล้ายกับ "ไม่มีองค์ประกอบ" ซึ่งคำตอบที่ถูกต้องคือ BTW ไม่true
false
นี่คือสิ่งที่ใช้การตรวจสอบครั้งแรกเทียบกับครั้งสุดท้าย (แม้ว่าฉันจะรวม "ค่าคงที่" ไว้ใน "การเพิ่มขึ้น") และทำให้ผู้โทรเป็นภาระในการป้อนข้อมูลที่สมเหตุสมผล (เช่นไม่ใช่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:]))
ฉันไม่ใช่แฟนตัวยงของการมีฟังก์ชันเสาหินเดียวที่ตรวจสอบความน่าเบื่อทั้งที่เพิ่มขึ้นและลดลง ในสถานการณ์จริงส่วนใหญ่ฉันคิดว่าคุณอาจจำเป็นต้องรู้ว่ามันเพิ่มขึ้นหรือลดลง
ตามที่ฉันกำหนดโดยเฉพาะ:
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
สิ้นสุดของลูปหมายความว่าอาร์เรย์เป็นโมโนโทนิกอย่างแน่นอน นอกจากนี้ยังมีการใช้ข้อสังเกตเกี่ยวกับอันตรายของการมีnumbers.length-1
เงื่อนไขการวนซ้ำด้วย