面接問題38:数字がソート配列に現れる回数
10478 ワード
一.タイトル
1つの数値がソート配列に現れる回数を統計する.例えば、入力ソート配列{1,2,3,3,3,4,5}と数字3は、この配列に3が4回現れるため、出力4となる.
コードは私のコードライブラリにPoint 2 Offerをダウンロードしてください
二.コード#コード#
不適切な点がありましたら、お知らせください.
1つの数値がソート配列に現れる回数を統計する.例えば、入力ソート配列{1,2,3,3,3,4,5}と数字3は、この配列に3が4回現れるため、出力4となる.
コードは私のコードライブラリにPoint 2 Offerをダウンロードしてください
二.コード#コード#
package ween_2;
/** :***
* offer:
* :
* : ( , 1 , , , )
* ( , )
* @author dingding
* Date:2017-6-27 20:00
* Declaration: All Rights Reserved!
*/
public class No38 {
public static void main(String[] args) {
test1();
test2();
test3();
test4();
test5();
test6();
test7();
}
// k
private static int getFirstK(int[] array,int length,int k,int start,int end){
if (start>end) {
return -1;
}
int middleIndex = (start+end)/2;
int middleData = array[middleIndex];
if (middleData == k) {
if ((middleIndex > 0 && array[middleIndex-1]!=k) || middleIndex==0) {
return middleIndex;
}else {
end = middleIndex-1;
}
}else if (middleData>k) {
end = middleIndex - 1;
}else {
start = middleIndex + 1;
}
return getFirstK(array, length, k, start, end);
}
// k
private static int getLastK(int[] array,int length,int k,int start,int end){
if (start>end) {
return -1;
}
int middleIndex = (start+end)/2;
int middleData = array[middleIndex];
if (middleData==k) {
if ((middleIndex1 && array[middleIndex+1]!=k) || middleIndex==length-1) {
return middleIndex;
}else {
start = middleIndex+1;
}
}else if(middleData1;
}else {
end = middleIndex - 1;
}
return getLastK(array, length, k, start, end);
}
//
private static int getNumberOfK(int[] array,int length,int k){
int number = 0;
if (array == null || length<1) {
return -1;
}
if (array != null && length>0) {
int first = getFirstK(array, length, k, 0, length-1);
int last = getLastK(array, length, k, 0, length-1);
if (first>-1 && last > -1) {
number = last - first +1;
}
}
return number;
}
/*================== ================*/
private static void test(int[] array,int length,int k){
int result = getNumberOfK(array, length, k);
if (result != -1) {
System.out.println(k+" : "+ result);
}else{
System.out.println(" !");
}
System.out.println("====================");
}
private static void test1() {
int[] array = {1,2,3,4,5,5,6};
int k=7;
test(array, array.length, k);
}
private static void test2() {
int[] array = {1,2,3,4,5,5,6};
int k=3;
test(array, array.length, k);
}
private static void test3() {
int[] array = {1,2,3,4,5,5,6};
int k=5;
test(array, array.length, k);
}
private static void test4() {
int[] array = {1,2,3,4,5,5,6};
int k=6;
test(array, array.length, k);
}
private static void test5() {
int[] array = {1,2,3,4,5,5,6};
int k=1;
test(array, array.length, k);
}
private static void test6() {
int[] array = {1};
int k=1;
test(array, array.length, k);
}
private static void test7() {
int[] array = {};
int k=6;
test(array, array.length, k);
}
}
不適切な点がありましたら、お知らせください.