爪哇国新游记之二十七

爪哇国新游记之二十七"/>

爪哇国新游记之二十七

代码：

import java.util.ArrayList;
import java.util.List;public class Bit {int max;int min;int[] arr;public Bit(int[] arrInput) {// 找出极值for (int i = 0; i < arrInput.length; i++) {if (max < arrInput[i]) {max = arrInput[i];}if (min > arrInput[i]) {min = arrInput[i];}}// 新建数组arr = new int[max - min + 1];// 数组插值for (int i : arrInput) {int index = i - min;arr[index]++;}}public boolean hasDuplicateItem() {for (int i = 0; i < arr.length; i++) {int value = arr[i];if (value > 1) {return true;}}return false;}public List<Integer> getSortedList() {List<Integer> ls = new ArrayList<Integer>();for (int i = 0; i < arr.length; i++) {int value = arr[i];if (value != 0) {for (int j = 0; j < value; j++) {ls.add(min + i);}}}return ls;}public List<Integer> getUniqueSortedList() {List<Integer> ls = new ArrayList<Integer>();for (int i = 0; i < arr.length; i++) {int value = arr[i];if (value != 0) {ls.add(min + i);}}return ls;}public int[] getUniqueSortedArray(){List<Integer> ls=getUniqueSortedList();int[] arr=new int[ls.size()];for(int i=0;i<arr.length;i++){arr[i]=ls.get(i);}return arr;}/*** 二分查找* * @param sortedArray*            已排序的欲查找的数组* @param seachValue*            查找的值* @return 找到的元素下标，若找不到则返回-1*/public static int binSearch(int[] sortedArray, int seachValue) {// 左边界int leftBound = 0;// 右边界int rightBound = sortedArray.length - 1;// 当前下标位置int curr;while (true) {// 定位在左边界和右边界中间curr = (leftBound + rightBound) / 2;if (sortedArray[curr] == seachValue) {// 找到值return curr;} else if (leftBound > rightBound) {// 左边界大于右边界，已经找不到值return -1;} else {if (sortedArray[curr] < seachValue) {// 当当前下标对应的值小于查找的值时，缩短左边界leftBound = curr + 1;} else {// 当当前下标对应的值大于查找的值时，缩短右边界rightBound = curr - 1;}}}}public static void main(String[] args) {int[] arr = { -2, -1, 3, 5, 7, 9, 30, 4, -2, 5, 8, 3 };Bit b = new Bit(arr);System.out.println("排序后数组");int[] arr2=b.getUniqueSortedArray();for(int i=0;i<arr2.length;i++){System.out.println(i+":"+arr2[i]);}int[] arr3={2,5,7,-2,90};for(int i=0;i<arr3.length;i++){int index=Bit.binSearch(arr2, arr3[i]);if(index!=-1){System.out.println(arr3[i]+"排在数组arr2的第"+index+"个");}else{System.out.println(arr3[i]+"不在数组arr2中");}}}
}

输出：

排序后数组
0:-2
1:-1
2:3
3:4
4:5
5:7
6:8
7:9
8:30
2不在数组arr2中
5排在数组arr2的第4个
7排在数组arr2的第5个
-2排在数组arr2的第0个
90不在数组arr2中

本文转自张昺华-sky博客园博客，原文链接：.html，如需转载请自行联系原作者