Seguimiento de «Encontrar mínimo en matriz ordenada rotada»: ¿Qué sucede si se permiten duplicados?
¿Afectaría esto la complejidad del tiempo de ejecución? ¿Como y por qué?
Solución Java 1: recursividad
Este es un problema de seguimiento de encontrar un elemento mínimo en una matriz ordenada rotada sin elementos duplicados. Solo necesitamos agregar una condición más, que verifica si el elemento más a la izquierda y el elemento más a la derecha son iguales. Si es así, simplemente podemos soltar uno de ellos. En mi solución a continuación, dejo caer el elemento izquierdo siempre que el más a la izquierda sea igual al más a la derecha.
public int findMin(int[] num) { return findMin(num, 0, num.length-1); } public int findMin(int[] num, int left, int right){ if(right==left){ return num[left]; } if(right == left +1){ return Math.min(num[left], num[right]); } // 3 3 1 3 3 3 int middle = (right-left)/2 + left; // already sorted if(num[right] > num[left]){ return num[left]; //right shift one }else if(num[right] == num[left]){ return findMin(num, left+1, right); //go right }else if(num[middle] >= num[left]){ return findMin(num, middle, right); //go left }else{ return findMin(num, left, middle); } } |
Solución Java 2: iteración
public int findMin(int[] nums) { int i=0; int j=nums.length-1; while(i<=j){ //handle cases like [3, 1, 3] while(nums[i]==nums[j] && i!=j){ i++; } if(nums[i]<=nums[j]){ return nums[i]; } int m=(i+j)/2; if(nums[m]>=nums[i]){ i=m+1; }else{ j=m; } } return -1; } |
