【演算法】在排序陣列中查找元素的開始位置和結束位置
一.問題描述：
1.輸入：輸入一個已經升序排列的整數型陣列arr和一個目標值target，
2.輸出：輸出這個目標值target在陣列中的開始位置和結束位置的索引，若target在陣列中不存在，則回傳[-1,-1]，
3.比如：輸入{5,7,7,8,8,10}，target=8 ;輸出[3,4]
? 輸入{5,7,7,8,8,10}，target=6;輸出[-1,-1]
? 輸入{5,7,7,8,8,810}，target=8;輸出[3,5]
? 輸入{5,7,7,8,8,8,10}，target=10;輸出[6,6]
? 輸入{5,7,7,8,8,8,10}，target=5;輸出[0,-1]
二.問題解答：
方法:線性掃描(即依次遍歷陣列)
第一次遍歷從左往右遍歷，直到找到開始位置的索引值；第二次遍歷從右往左遍歷，直到找到結束位置的索引值，
三.演算法分析：
1.時間復雜度為O(N)，額外空間復雜度為O（1），
代碼如下
import java.util.Arrays;
import java.util.Scanner;
/*
* 問題：在排序陣列中查找元素的開始位置和結束位置
*/
public class SearchRange {
public static void main(String[] args) {
Scanner in =new Scanner(System.in);
String str=in.nextLine();
int target=in.nextInt();
String [] strArray=str.split(",");
int[] arr=new int[strArray.length];
for(int i=0;i<arr.length;i++) {
arr[i]=Integer.valueOf(strArray[i]);
}
int[] result= SearchRange(arr, target);
System.out.println(Arrays.toString(result));
}
public static int [] SearchRange(int []arr,int target) {
int[] result= {-1,-1};
for(int i=0;i<arr.length;i++) {
if(arr[i]==target) {
result[0]=i;
break;
}
}
if(result[0]==-1) {
return result;
}
for(int j=arr.length-1;j>0;j--) {
if(arr[j]==target) {
result[1]=j;
break;
}
}
return result;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/184851.html
標籤：其他
下一篇：無限回圈？