8000 完成从排序数组中统计元素出现的个数。 · fleapx/javaalgorithm@2419492 · GitHub
[go: up one dir, main page]
Skip to content

Commit 2419492

Browse files
author
shengshijun
committed
完成从排序数组中统计元素出现的个数。
1 parent cc4af48 commit 2419492

File tree

2 files changed

+82
-5
lines changed

2 files changed

+82
-5
lines changed

‎src/main/java/ssj/algorithm/ArrayUtil.java

Lines changed: 76 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,6 @@
55
import ssj.algorithm.collections.BitSet;
66
import ssj.algorithm.collections.HashSet;
77
import ssj.algorithm.collections.TreeMap;
8-
import ssj.algorithm.lang.Tuple2;
98
import ssj.algorithm.math.MathUtil;
109

1110
import java.util.Comparator;
@@ -443,7 +442,83 @@ private static <T> boolean checkMoreThanHalf(T[] arr, T most_ele) {
443442
return count * 2 > arr.length;
444443
}
445444

445+
/**
446+
* 从一个排序的数组中查询某个元素出现的个数。
447+
*
448+
* @param arr
449+
* @param ele
450+
* @param <T>
451+
* @return
452+
*/
453+
public static <T extends Comparable<T>> int countEle(T[] arr, T ele) {
454+
Preconditions.checkNotNull(arr);
455+
Preconditions.checkNotNull(ele);
456+
int start = getFirstEle(arr, ele);
457+
int end = getLastEle(arr, ele);
458+
return (start != -1) ? (end - start + 1) : 0;
459+
}
446460

461+
/**
462+
* 从一个排序的数组中查询某个元素第一次出现的位置
463+
*
464+
* @param arr
465+
* @param ele
466+
* @param <T>
467+
* @return
468+
*/
469+
public static <T extends Comparable<T>> int getFirstEle(T[] arr, T ele) {
470+
Preconditions.checkNotNull(arr);
471+
Preconditions.checkNotNull(ele);
472+
int start = 0;
473+
int end = arr.length - 1;
474+
while (start <= end) {
475+
int mid = (start + end) / 2;
476+
int com_res = arr[mid].compareTo(ele);
477+
if (com_res == 0) {
478+
if (arr[mid].equals(arr[mid - 1])) {
479+
end = mid - 1;
480+
} else {
481+
return mid;
482+
}
483+
} else if (com_res > 0) {
484+
end = mid - 1;
485+
} else {
486+
start = mid + 1;
487+
}
488+
}
489+
return -1;
490+
}
491+
492+
/**
493+
* 从一个排序的数组中查询某个元素最后一次出现的位置。
494+
*
495+
* @param arr
496+
* @param ele
497+
* @param <T>
498+
* @return
499+
*/
500+
public static <T extends Comparable<T>> int getLastEle(T[] arr, T ele) {
501+
Preconditions.checkNotNull(arr);
502+
Preconditions.checkNotNull(ele);
503+
int start = 0;
504+
int end = arr.length - 1;
505+
while (start <= end) {
506+
int mid = (start + end) / 2;
507+
int com_res = arr[mid].compareTo(ele);
508+
if (com_res == 0) {
509+
if (arr[mid].equals(arr[mid + 1])) {
510+
start = mid + 1;
511+
} else {
512+
return mid;
513+
}
514+
} else if (com_res > 0) {
515+
end = mid - 1;
516+
} else {
517+
start = mid + 1;
518+
}
519+
}
520+
return -1;
521+
}
447522
}
448523

449524

‎src/test/java/ssj/algorithm/ArrayUtilTest.java

Lines changed: 6 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,12 @@
11
package ssj.algorithm;
22

33
import org.junit.Test;
4-
import ssj.algorithm.lang.Tuple2;
5-
import ssj.algorithm.math.MathUtil;
64
import ssj.algorithm.string.StringBuilder;
75

86
import java.util.Arrays;
97

10-
import static org.junit.Assert.*;
8+
import static org.junit.Assert.assertEquals;
9+
import static org.junit.Assert.assertTrue;
1110

1211
/**
1312
* Created by shenshijun on 15/2/13.
@@ -80,7 +79,10 @@ public void testMoreThanHalfEle() {
8079
assertEquals(Integer.valueOf(2), ArrayUtil.moreThanHalfEle(data));
8180
}
8281

83-
82+
@Test
83+
public void testCountEle() {
84+
assertEquals(4, ArrayUtil.countEle(new Integer[]{1,2,3,3,3,3,4,5,102,2873}, 3));
85+
}
8486

8587

8688
}

0 commit comments

Comments
 (0)
0