Controllare se l'array è monotono, ovvero monotono in aumento o monotono in diminuzione
Un array A è monotono crescente se per tutti i <= j, A [i] <= A [j]. Un array A è monotono decrescente se per tutti i <= j, A [i]> = A [j].
Restituisce vero se e solo se l'array A dato è monotono.
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;
}
}
Casi test:
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));
}
}
Risposte
statico
IsMonotonic(...)non necessita di un'istanza della MonotonicArrayclasse per funzionare, quindi dovrebbe essere statica.
Consistenza
Caso speciale un array di lunghezza 1 come monotono. É davvero? Non è né in aumento né in diminuzione.
Di cosa IsMonotonic(new int[]{1, 1, 1, 1})? Mi sembra che dovrebbe essere true, ma tornerà false. Sicuramente dovrebbe essere aggiunto come caso di prova. E se dovesse tornare true, allora ...
Ottimizzazione
... il controllo della lunghezza 1 è troppo restrittivo. Anche qualsiasi array di lunghezza 2 sarà sempre monotono. Forse:
if (numbers.length == 1) {
return true;
}
dovrebbe essere:
if (numbers.length <= 2) {
return true;
}
Looping
Questo è brutto. Java ottimizzerà il numbers.length - 1calcolo come costante?
for (int index = 0; index < numbers.length - 1; index++) {
if (numbers[index + 1] == numbers[index]){
continue;
}
...
Potrebbe essere meglio utilizzare il forciclo avanzato di Java per estrarre i numeri e fare affidamento su un comportamento monotono che consenta all'uguaglianza di gestire il primo elemento:
int current = numbers[0];
for(int value : numbers) {
if (value != current) {
if (value < current) {
...
} else {
...
}
current = value;
}
}
Il ciclo è piuttosto complicato. In genere è meglio usare una logica più semplice, se possibile, in quanto ciò rende il ciclo più semplice da ragionare. Ad esempio, puoi utilizzare Integer.compareper rimuovere molta logica dal tuo ciclo.
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;
}
In ogni iterazione la cmpvariabile è zero se i due numeri sono uguali e positiva o negativa a seconda che si sia verificato un aumento o una diminuzione.
Quando lastCmpè zero, dobbiamo ancora vedere un aumento o una diminuzione, cioè tutti i numeri interi sono stati uguali. Se lastCmpè diverso da zero, allora abbiamo visto un aumento o una diminuzione. Se la sequenza non è monotona, alla fine raggiungeremo una coppia che si è mossa nella direzione opposta rispetto al primo cambiamento, che è ciò che rileverà la seconda condizione.
Se l'elenco è più corto di due elementi, il ciclo non viene eseguito affatto e restituisce solo true.
Potresti ottenere prestazioni e semplicità migliori se decidi subito: il confronto del primo valore con l' ultimo valore ti dice immediatamente quale tra crescente / decrescente / costante dovresti controllare.
Quello che dovresti fare
nulldipende dal contratto. Questo problema è su LeetCode , dove sei persino garantito che l'array avrà almeno un elemento, quindi non avrai bisogno di coprirenullo un array vuoto. Hai "scelto" (?) Di ritornarefalse, ma potresti anche discutere a favoretrue, dato che "no array" sembra piuttosto simile a "no elements", per il quale la risposta corretta è btwtrue, nofalse.
Eccone uno che utilizza un controllo first-vs-last (anche se ho incluso "costante" in "crescente") e che pone l'onere sul chiamante di fornire un input ragionevole (cioè no null). Penso che sia meglio che l'utente riceva un errore piuttosto che fingere silenziosamente che non ci sia nulla di sbagliato.
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;
}
Una BiPredicateversione ispirata alla risposta di RoToRa . Questo distingue tutti e tre i casi, poiché BiPredicateevita la duplicazione del codice:
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;
}
Versione Python, solo per divertimento :-)
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:]))
Non sono un grande fan di avere una singola funzione monolitica che controlla indiscriminatamente la monotonia sia in aumento che in diminuzione. Nella maggior parte degli scenari pratici immagino che probabilmente dovresti sapere se sta aumentando o diminuendo.
Sulla base di ciò definirei specificamente:
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
}
Certo, ci saranno un paio di controlli duplicati, ma alla fine IMO il codice sarà meglio strutturato, meglio leggibile e più riutilizzabile.
Se accetti l' osservazione di coerenza di @AJNeufeld (in modo che [1]essere monotono indichi che [1,1,1]potrebbe anche essere monotono) e metti di nuovo l'altra osservazione [x,y]sull'essere monotoni, potresti trovare più facile avere true-s per impostazione predefinita e riconoscere quando l'array non lo è monotono:
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;
}
Ovviamente sembra così ordinato solo senza cortocircuiti, dopodiché avrà di nuovo una struttura molto simile al tuo codice originale:
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;
}
Qui sono tornato all'accesso indicizzato sulla base della mia antipatia per il confronto del primo elemento con se stesso (cosa fa la for(:)variante). Si noti inoltre che qui, a causa del cortocircuito return, il completamento del ciclo significa che l'array è sicuramente monotono. Inoltre numbers.length-1è stata applicata anche l'osservazione sul rischio di avere nella condizione di loop.