Dada una matriz ordenada de números enteros, encuentre la posición inicial y final de un valor objetivo dado. La complejidad del tiempo de ejecución de su algoritmo debe ser del orden de O (log n). Si el objetivo no se encuentra en la matriz, regrese [-1, -1]. Por ejemplo, dado [5, 7, 7, 8, 8, 10] y valor objetivo 8, retorno [3, 4].
Análisis
Basado en el requisito de O (log n), este es un problema de búsqueda binaria aparentemente.
Solución 1 de Java: registro (n)
Primero podemos encontrar el inicio y luego el final del objetivo.
public int[] searchRange(int[] nums, int target) { int l=0; int r=nums.length-1; while(l<r){ int m=l+(r-l)/2; if(nums[m]<target){ l=m+1; }else{ r=m; } } int first=l; if(l<nums.length&&nums[l]==target){//l is in boundary and is the target l=0; r=nums.length-1; while(l<r){ int m=l+(r-l+1)/2; if(nums[m]>target){ r=m-1; }else{ l=m; } } return new int[]{first, r}; } return new int[]{-1,-1}; } |
Solución Java 2 – (obsoleta)
public int[] searchRange(int[] nums, int target) { if(nums == null || nums.length == 0){ return null; } int[] arr= new int[2]; arr[0]=-1; arr[1]=-1; binarySearch(nums, 0, nums.length-1, target, arr); return arr; } public void binarySearch(int[] nums, int left, int right, int target, int[] arr){ if(right<left) return; if(nums[left]==nums[right] && nums[left]==target){ arr[0]=left; arr[1]=right; return; } int mid = left+(right-left)/2; if(nums[mid]<target){ binarySearch(nums, mid+1, right, target, arr); }else if(nums[mid]>target){ binarySearch(nums, left, mid-1, target, arr); }else{ arr[0]=mid; arr[1]=mid; //handle duplicates - left int t1 = mid; while(t1 >left && nums[t1]==nums[t1-1]){ t1--; arr[0]=t1; } //handle duplicates - right int t2 = mid; while(t2 < right&& nums[t2]==nums[t2+1]){ t2++; arr[1]=t2; } return; } } |
En el peor de los casos, el tiempo de la segunda solución es en realidad O (n).
