ソート配列に数値が表示される回数(Java)
2116 ワード
タイトル:
ソート配列に表示される数値の回数を統計します.例えばソート配列{1,2,3,3,3,3,4,5}と数字3を入力し,3がこの配列に4回出現したため4を出力する.
考え方:
第1の解法:蛮力法、配列を順番に遍歴して、数字の3の出現の回数を統計して、しかしこの時テーマの中で与える秩序を利用していないで、だから時間は複雑で大きくて、要求に合いません.
第2の解法:二分探索の思想(時間複雑度log(n))を利用して問題を解決する.まず、配列中の3が現れる最初の位置first 3を見つけてから、配列中の3が最後に現れる位置end 3を見つけて、first 3-end 3+1は数字3が現れる回数です.
コード実装:
ソート配列に表示される数値の回数を統計します.例えばソート配列{1,2,3,3,3,3,4,5}と数字3を入力し,3がこの配列に4回出現したため4を出力する.
考え方:
第1の解法:蛮力法、配列を順番に遍歴して、数字の3の出現の回数を統計して、しかしこの時テーマの中で与える秩序を利用していないで、だから時間は複雑で大きくて、要求に合いません.
第2の解法:二分探索の思想(時間複雑度log(n))を利用して問題を解決する.まず、配列中の3が現れる最初の位置first 3を見つけてから、配列中の3が最後に現れる位置end 3を見つけて、first 3-end 3+1は数字3が現れる回数です.
コード実装:
public class Main {
// k
private int getFirstK(int nums[], int k, int start, int end){
if(start > end){
return -1;
}
int middleIndex = (start + end) /2;
int middleData = nums[middleIndex];
if(middleData == k){
// k : middleIndex=0; middleIndex > 0 middleIndex-1 k
if((middleIndex > 0 && nums[middleIndex-1]!=k) || middleIndex == 0){
return middleIndex;
}else{
end = middleIndex -1;
}
}else if(middleData > k){
end = middleIndex - 1;
}else{
start = middleIndex + 1;
}
return getFirstK(nums, k, start, end);
}
// k
private int getLastK(int nums[], int k, int start, int end){
if(start > end){
return -1;
}
int middleIndex = (start + end) / 2;
int middleData = nums[middleIndex];
if(middleData == k){
// k : middleIndex= -1; middleIndex < len-1 middleIndex+1 k
if((middleIndex < nums.length -1 && nums[middleIndex + 1] != k) || middleIndex == nums.length -1){
return middleIndex;
}else{
start = middleIndex + 1;
}
}else if(middleData < k){
start = middleIndex + 1;
}else{
end = middleIndex -1;
}
return getLastK(nums, k, start, end);
}
public int getNumberOfK(int nums[], int k){
int number = 0;
int len = nums.length;
if(nums != null && len > 0){
int firstK = getFirstK(nums, k, 0, len-1);
int lastK = getLastK(nums, k, 0, len-1);
if(firstK > -1 && lastK > -1){
number = lastK - firstK + 1;
}
}
return number;
}
public static void main(String[] args) {
Main m1 = new Main();
int nums[] = new int[]{1, 2, 3, 3, 3, 3, 4, 5};
int count = m1.getNumberOfK(nums, 3);
System.out.println(count);
}
}