Periksa apakah array monotonik yaitu monoton meningkat atau monoton menurun
Array A monoton meningkat jika untuk semua i <= j, A [i] <= A [j]. Sebuah array A monoton menurun jika untuk semua i <= j, A [i]> = A [j].
Kembalikan nilai benar jika dan hanya jika larik A yang diberikan monotonik.
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;
}
}
Kasus uji:
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));
}
}
Jawaban
statis
IsMonotonic(...)tidak memerlukan turunan MonotonicArraykelas untuk berfungsi, oleh karena itu harus statis.
Konsistensi
Anda kasus khusus array dengan panjang 1 sebagai monotonik. Benarkah? Itu tidak meningkat atau menurun.
Tentang apa IsMonotonic(new int[]{1, 1, 1, 1})? Menurut saya itu seharusnya true, tetapi itu akan kembali false. Pasti harus ditambahkan sebagai kasus uji. Dan jika itu harus kembali true, maka ...
Optimasi
... memeriksa panjang 1 terlalu membatasi. Setiap panjang 2 larik akan selalu monotonik juga. Mungkin:
if (numbers.length == 1) {
return true;
}
seharusnya:
if (numbers.length <= 2) {
return true;
}
Pendauran
Ini jelek. Akankah Java mengoptimalkan numbers.length - 1penghitungan sebagai konstanta?
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
...
Mungkin lebih baik menggunakan forloop yang ditingkatkan Java untuk mengekstrak angka, dan mengandalkan perilaku monotonik yang memungkinkan persamaan untuk menangani elemen pertama:
int current = numbers[0];
for(int value : numbers) {
if (value != current) {
if (value < current) {
...
} else {
...
}
current = value;
}
}
Perulangannya agak rumit. Biasanya lebih baik menggunakan logika yang lebih sederhana jika memungkinkan, karena itu membuat loop lebih sederhana untuk dipikirkan. Misalnya, Anda dapat menggunakan Integer.compareuntuk menghapus banyak logika dari loop Anda.
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;
}
Dalam setiap iterasi cmpvariabel bernilai nol jika kedua bilangan tersebut sama, dan bisa positif atau negatif bergantung pada apakah ada kenaikan atau penurunan.
Ketika lastCmpnol, kita belum melihat kenaikan atau penurunan, yaitu semua bilangan bulat adalah sama. Jika lastCmpbukan nol, maka kita telah melihat peningkatan atau penurunan. Jika urutannya tidak monoton, pada akhirnya kita akan mencapai pasangan yang bergerak berlawanan arah dari perubahan pertama, yang akan dideteksi oleh kondisi kedua.
Jika daftar lebih pendek dari dua elemen, maka loop tidak berjalan sama sekali, dan hanya mengembalikan nilai true.
Anda mungkin mendapatkan kinerja yang lebih baik dan kesederhanaan jika Anda membuat pikiran Anda segera: Membandingkan pertama nilai dengan terakhir nilai segera memberitahu Anda yang salah satu peningkatan / penurunan / konstan Anda harus memeriksa.
Apa yang harus Anda lakukan
nulltergantung pada kontrak. Masalah ini ada di LeetCode , di mana Anda bahkan dijamin bahwa array akan memiliki setidaknya satu elemen, jadi di sana Anda tidak perlu menutupinullatau array kosong. Anda "memilih" (?) Untuk kembalifalse, tetapi Anda juga bisa membantahnyatrue, karena "tidak ada larik" tampaknya agak mirip dengan "tanpa elemen", yang jawaban yang benar adalah btwtrue, bukanfalse.
Ini adalah salah satu yang menggunakan pemeriksaan pertama-vs-terakhir (meskipun saya menyertakan "konstan" dalam "meningkat") dan yang membebani pemanggil untuk memberikan masukan yang masuk akal (yaitu, tidak null). Saya pikir lebih baik membuat pengguna mendapatkan kesalahan daripada diam-diam berpura-pura tidak ada yang salah.
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;
}
Sebuah BiPredicateversi yang terinspirasi oleh jawaban RoToRa . Yang ini membedakan ketiga kasus, karena BiPredicatemenghindari duplikasi kode:
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;
}
Versi Python, hanya untuk bersenang-senang :-)
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:]))
Saya bukan penggemar berat memiliki fungsi monolitik tunggal yang tanpa pandang bulu memeriksa peningkatan dan penurunan monoton. Dalam kebanyakan skenario praktis, saya membayangkan Anda mungkin perlu tahu apakah itu meningkat atau menurun.
Berdasarkan itu saya akan mendefinisikan secara khusus:
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
}
Tentu, akan ada beberapa pemeriksaan duplikat, tetapi pada akhirnya kode IMO akan lebih terstruktur, lebih mudah dibaca, dan lebih dapat digunakan kembali.
Jika Anda menerima komentar konsistensi @AJNeufeld (sehingga [1]menjadi monoton menunjukkan bahwa [1,1,1]mungkin juga monotonik) dan meletakkan komentar lain tentang [x,y]menjadi monotonik lagi, Anda mungkin merasa lebih mudah untuk memiliki true-s secara default dan mengenali ketika array tidak monoton:
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;
}
Tentu saja terlihat rapi hanya tanpa korsleting, setelah itu akan memiliki struktur yang sangat mirip dengan kode asli Anda lagi:
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;
}
Di sini saya kembali ke akses yang diindeks atas dasar ketidaksukaan saya terhadap perbandingan elemen pertama dengan dirinya sendiri (apa yang dilakukan for(:)varian). Perhatikan juga bahwa di sini, karena korsleting return, penyelesaian loop berarti bahwa array pasti monoton. Ditambah komentar tentang bahaya memiliki numbers.length-1kondisi loop telah diterapkan juga.