其他
笔试编程 | 二分查找、数组、排序
原理：将数组分为三部分，依次是中值（所谓的中值就是数组中间位置的那个值）前，中值，中值后，将要查找的值和数组的中值进行比较，若小于中值则在中值前面找，若大于中值则在中值后面找，等于中值时直接返回。然后依次是一个递归过程，将前半部分或者后半部分继续分解为三部分。
public class BinarySearch {
//循环实现二分查找
public static int binarySearch(int[] arr, int x) {
int low = 0;
int high = arr.length - 1;
while (low <= high) {
int middle = (low + high) / 2;
if (x == arr[middle]) {
return middle;
} else if (x < arr[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
//无法查到数据
return -1;
}
//递归实现二分查找
public static int binarySearch(int[] dataset, int data, int beginIndex, int endIndex) {
int midIndex = (beginIndex + endIndex) / 2;
if (data < dataset[beginIndex] || data > dataset[endIndex] || beginIndex > endIndex) {
return -1;
}
if (data < dataset[midIndex]) {
return binarySearch(dataset, data, beginIndex, midIndex - 1);
} else if (data > dataset[midIndex]) {
return binarySearch(dataset, data, midIndex + 1, endIndex);
} else {
return midIndex;
}
}
public static void main(String[] args) {
int[] arr = {6, 12, 33, 87, 90, 97, 108, 561};
System.out.println("循环查找：" + (binarySearch(arr, 87) + 1));
System.out.println("递归查找" + binarySearch(arr, 3, 87, arr.length - 1));
}
}1.对正整数进行分解质因数
// 如传入100, 打印出2*2*5*5
/** 思路:
* 首先找到一个最小的质数i
* 1. 如果这个质数恰等于num, 则说明分解质因数的过程已经结束, 打印出即可
* 2. 如果num > i, 但num能被i整除, 则打印出i的值, 并用num除以i的商, 作为新的正整数num, 重复执行第一步
* 3. 如果num不能被i整除, 则用i+1作为i的值, 重复执行第一步
**/
public static void t0(int num) {
for (int i = 2; i <= num; i++) {
while (num != i) {
if (num % i == 0) {
System.out.print(i + "*");
num = num / i;
} else {
break;
}
}
}
System.out.println(num);
}2.在一个给定的从1到100的整型数组中，快速找到缺失的数字
/**思路:
* 1. 首先对集合进行升序排序
* 2. 在没有确实数字的情况下, `排序后`相邻间的两数字差值应为1, 需要处理的是差值大于1的 [差值为1和差值为0的不需要处理]
*
* @param arr 正整数数组 如int[] list = {1, 10, 4, 2, 8, 3, 2, 13};
**/
public static void t1(int[] arr) {
if (arr != null) {
ArrayList<Integer> nums = new ArrayList<Integer>();
int length = arr.length;
if (length == 1) {
System.out.println(nums);
}
Arrays.sort(arr);
for (int i = 0; i < length; i++) {
if (i != length - 1) {
int now = arr[i];
int step = arr[i + 1] - now;
if (step > 1) {
int x = 0;
while (x < step - 1) {//注意临界值的处理
x++;
nums.add(now + x);
}
}
}
}
System.out.println(nums);
}
}3.对字符串进行中的数字进行正序排序，并且字符串中字母的位置不变
//如，43a6f9d8, 输出34a6f8d9
/**思路:
* 1. 先遍历字符串取出其中的数字放进一个集合, 然后对集合进行正序排序
* 2. 再次遍历字符串, 遇到字符为数字的, 取出数字字符集合numChars中的第一个元素(索引j=0)放在此位置, 并对numChars下一个取出的元素索引定位为j++
**/
public static String t3(String str) {
if (StringUtils.isBlank(str)) {
return str;
}
ArrayList<Character> numChars = new ArrayList<>();
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char c = chars[i];
if (Character.isDigit(c)) {
numChars.add(c);
}
}
Collections.sort(numChars);
StringBuilder builder = new StringBuilder();
for (int i = 0, j = 0; i < chars.length; i++) {
char c = chars[i];
if (Character.isDigit(c)) {
builder.append(numChars.get(j));
j++;
} else {
builder.append(c);
}
}
return builder.toString();
}4.在一个未排序的整型数组中, 找到最大和最小的数字
// 如，int[] list = {-2, 1, 99, 10, 4, 2, -1, 8, 3, 2, 13, 0}；输出max: 99 ; min: -2
/**思路:
* 1. 初始化最大数字max和最小数字min为数组中第一个元素
* 2. 将max和数组中"下一个"元素next比较, 如果next>max, 则max=next
* 3. 将min和数组中"下一个"元素next比较, 如果next<min,则min=next
**/
public static void t4(int[] arr) {
if (arr != null) {
int length = arr.length;
if (length == 1) {
System.out.println("the max num and min num both are: " + arr[0]);
} else {
int max = 0;
int min = 0;
for (int i = 0; i < length; i++) {
int num = arr[i];
if (i == 0) {
max = num;
min = num;
} else {
if (num > max) {
max = num;
}
if (num < min) {
min = num;
}
}
}
System.out.println("max num is: " + max + " ; min num is: " + min);
}
}
}5.一个整型数组中，找到一个所有成对的数字，满足它们的和等于一个给定的数字
//如，int[] arr = {-2, 1, 99, 10, 4, 2, -1, 8, 3, 2, 13}, sum为3; 找出 -1和4, 1和2即可;
//如，int[] arr = {1, 1, 2, 3, 3, 1, 2, 0, 0}, sum为3; 找出1和2, 3和0即可
public static void t5_0(int[] arr, int sum) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
HashSet<String> set = new HashSet<>();
for (int i = 0, j = length - 1; i < j; ) {
int tmpSum = arr[i] + arr[j];
if (tmpSum == sum) {
//如果只获取其中一对元素和等于sum直接return
//return arr[i] + "+" + arr[j] + "=" + sum;
//如果是获取所有并且不重复可以采取这种
set.add(arr[i] + "+" + arr[j] + "=" + sum);
//避免进入死循环
i++;
j--;
} else if (tmpSum < sum) {
i++;
} else {
j--;
}
}
System.out.println(set);
}
}6.如果一个数组包含多个重复元素，找到这些重复的数字
//如，int[] arr = {1, 1, 2, 3, 3, 4, 2, 0, 0}；输出0,1,2,3即可
public static void t6(int[] arr) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
HashSet<Integer> res = new HashSet<>();
for (int i = 0; i < length; i++) {
if (i != length - 1) {
int now = arr[i];
int next = arr[i + 1];
if (now == next) {
res.add(now);
}
}
}
System.out.println(res);
}
}7.Java 实现从一个给定数组中删除重复元素
//如，int[] arr = {1, 1, 2, 3, 3, 4, 2, 0, 0}；输出 4
public static void t7(int[] arr) {
if (arr != null) {
int length = arr.length;
Arrays.sort(arr);
ArrayList<Integer> res = new ArrayList<>();
ArrayList<Integer> repeatNums = new ArrayList<>();
for (int i = 0; i < length; i++) {
int now = arr[i];
res.add(now);
if (i != length - 1) {
int next = arr[i + 1];
if (now == next) {
repeatNums.add(now);
}
}
}
res.removeAll(repeatNums);
System.out.println(res);
}
}8.Java实现数组反转
public static Object t8(int[] arr) {
if (arr != null) {
// 可以采用t8_t方法比较通用
//t8_t(arr, 0, arr.length);
int i = 0;
for (int j = arr.length - 1; j > i; ++i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
--j;
}
}
return ArrayUtils.toString(arr);
}
private static void t8_t(int[] arr, int startIndexInclusive, int endIndexExclusive) {
if (arr != null) {
int i = startIndexInclusive < 0 ? 0 : startIndexInclusive;
for (int j = Math.min(arr.length, endIndexExclusive) - 1; j > i; ++i) {
int tmp = arr[j];
arr[j] = arr[i];
arr[i] = tmp;
--j;
}
}
}1.快速排序（这里给出两种实现方法）
/**思路:
* 1. 在数据集中,选择一个元素作为"基准(pivot)"
* 2. 分区(partition)：所有小于"基准"的元素，都移到"基准"的左边；所有大于"基准"的元素都移到"基准"的右边
* 3. 分区操作结束后，基准元素所处的位置就是最终排序后它所处的位置
* 4. 对"基准"左边和右边的两个子集，不断重复第一步和第二步，直到所有子集都只剩下一个元素为止
*
* @param arr 待排序数组
* @param low 数组第一个元素索引
* @param high 数组最后一个元素的索引
* @return 排序后的数组
*/
public static int[] quickSort(int[] arr,int low,int high) {
//对low和high进行大小判断(此处如果仅对数组arr做非空及是否有元素判断会出现栈溢出)
if(low >= high) {
return arr;
}
//将arr一分为二
int middleIndex = partition(arr,low,high);
//对基准左边的进行递归排序
quickSort(arr,low,middleIndex-1);
//对基准右边的进行递归排序
quickSort(arr,middleIndex+1,high);
return arr;
}
/**获得"基准"(默认是最低位low)在数组排序后所在位置
* @param arr 待查找数组
* @param low 开始位置
* @param high 结束位置
* @return "基准"所在位置
*/
private static int partition(int[] arr, int low, int high) {
//每次都假设数组第一个位置的元素作为基准
int temp = arr[low];
while (low < high) {
while (arr[high] >= temp && high > low) {//后半部分向前扫描
//将临时基准元素与其右边的元素依次比较,值大于等于它的将high--
//当low<=high时,获取到等于或小于临时基准元素的元素
high--;
}
//将小于或等于基准元素的元素移到基准元素左边最低端
arr[low] = arr[high];
while (arr[low] <= temp && high > low) {//从前半部分扫描
low++;
}
//将大于或等于基准元素的元素移到基准元素右边最高端
arr[high] = arr[low];
}
//基准值
arr[low] = temp;
//返回最终基准
return low;
}2.选择排序（这里给出两种实现方法）
/** 思路:
* 1. 首先从未排序的序列中找到最小的元素, 放到排序序列的起始位置
* 2. 然后从剩余的未排序序列中继续查找最小元素, 放置到已排序序列的末尾
*
* 双层for循环: 遍历次数为数组长度-1, 外层for循环遍历索引从0到arr.length-2; 内层for循环遍历索引从1到arr.length-1
*/
public static int[] selectionSort(int[] arr) {
//判断数组是否为空及是否有元素
if(arr==null || arr.length==0) {
return arr;
}
//数组中有元素
//外层循环遍历数组目的是获取数组元素索引
for (int i = 0; i < arr.length - 1; i++) {
//将每个索引都假设为最小值的索引
int min = i;
for (int j = i + 1; j < arr.length; j++) {
//此时min=i, 将min位置的值跟其余的值比较
if(arr[j] < arr[min]) {
//索引j处的值比假设最小值小
min = j;
}
}
//元素位置交换获取升序排序(元素相同的0 0)
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
return arr;
}
/**方法2:
* 双层for循环: 遍历次数都是数组长度, 遍历索引都是从0到arr.length-1
*/
public static int[] selectSort(int[] arr) {
//判断数组是否为空及是否有元素
if(arr==null || arr.length==0) {
return arr;
}
int length = arr.length;
for (int i = 0; i < length; i++) {
int k = i;//待确定位置
//选择出应该在第i个位置的数
for (int j = length - 1; j > i; j--) {
if(arr[j] < arr[k]) {
k = j;
}
}
//交换两个数
int temp = arr[i];
arr[i] = arr[k];
arr[k] = temp;
}
return arr;
}
3.冒泡排序
/**思路:
* 1. 依次比较相邻的元素, 如果第一个比第二个大, 就交换他们两个的位置
* 2. 对每一对相邻元素作同样的操作, 从开始第一对到结尾的最后一对. 在这一点, 最后的元素应该会是最大的数
* 3. 针对所有的元素重复以上的步骤, 除了最后n个【n代表比较相邻元素的循环次数, 如第一次循环比较结束出去最后一个元素n=1】
* 4. 持续每次对越来越少的元素重复上面的步骤, 直到没有任何一对数字需要比较
*/
public static int[] bubbleSort(int[] arr) {
//对数组进行非空及是否有元素判断
if(arr==null || arr.length==0) {
return arr;
}
//每次循环都去掉最后面的i-1个元素，i代表循环次数
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length - i - 1; j++) {
//如果相邻的两个元素,前一个比后一个大则进行交换位置
if(arr[j]>arr[j+1]) {
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
return arr;
}4.插入排序
/**思路:
* 1. 认为第一个元素是排好序的, 从第二个开始遍历
* 2. 拿当前的元素, 从排好序的序列从中后往前找
* 3. 如果序列中的元素比当前元素大, 就把它后移, 直到找到一个小的
* 4. 将当前元素放在这个小的后面
*/
public static int[] insertionSort(int[] arr) {
//对数组进行非空及是否有元素判断
if(arr==null || arr.length==0) {
return arr;
}
for (int i = 0; i < arr.length; i++) {
for (int j = i; j > 0; j--) {
//相邻两个元素比较,如果前一个大于后一个则交换二者的位置
if(arr[j] < arr[j-1]) {
int temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
}
}
return arr;
}5.希尔排序
/**思路:
* 1. 先取一个正整数d1(d1 < n), 把全部记录分成d1个组, 所有元素之间距离为d1的倍数的记录看成一组, 然后在各组内进行插入排序
* 2. 然后取d2(d2 < d1)
* 3. 重复上述分组和排序操作, 直到取di = 1(i >= 1)位置, 即所有记录成为一个组, 最后对这个组进行插入排序.
*
* 一般选d1约为n/2, d2为d1/2, d3为d2/2 ... di = 1, n为数组元素个数
*
* 根据需求, 如果你想要结果从大到小排列, 它会首先将数组进行分组, 然后将较大值移到前面, 较小值移到后面, 最后将整个数组进行插入排序, 这样比起一开始就用插入排序减少了数据交换和移动的次数, 可以说希尔排序是加强版的插入排序
* 拿数组5, 2, 8, 9, 1, 3，4来说, 数组长度为7, 当increment为3时, 数组分为两个序列5、2、8和9、1、3、4, 第一次排序, 9和5比较, 1和2比较, 3和8比较, 4和比其下标值小increment的数组值相比较
*
* 此例子是按照从大到小排列, 所以大的会排在前面, 第一次排序后数组为9、2、8、5、1、3、4
* 第一次后increment的值变为3/2=1, 此时对数组进行插入排序, 实现数组从大到小排
*/
public static int[] shellSort(int[] arr) {
//对数组进行非空及是否有元素判断
if(arr==null || arr.length==0) {
return arr;
}
for (int gap = arr.length/2; gap > 0 ; gap/=2) {
for (int i = gap; i < arr.length; i++) {
int j = i;
while (j-gap>=0 && arr[j]<arr[j-gap]) {
int temp = arr[j];
arr[j] = arr[j-gap];
arr[j-gap] = temp;
j -= gap;
}
}
}
return arr;
}6.大顶堆排序
/**思路:
* 1. 将待排序的序列构建成一个大顶堆
* 2. 堆排序就是把最大堆堆顶的最大数取出, 将剩余的堆继续调整为最大堆, 再次将堆顶的最大数取出, 这个过程持续到剩余数只有一个时结束
*
* 最大堆调整: 将堆的末端子节点作调整, 使得子节点永远小于父节点
* 创建最大堆: 将堆所有数据重新排序, 使其成为最大堆
* 堆排序: 移除位于第一个数据的根节点, 并做最大堆调整的递归运算
*/
public static int[] heapSort(int[] arr) {
for (int i = arr.length / 2; i >= 0; i--) {
heapAdjust(arr, i, arr.length);
}
//逐步将每个最大值的根节点与末尾元素交换, 并且再调整二叉树, 使其成为大顶堆
for (int i = arr.length - 1; i > 0; i--) {
//进行元素位置交换
swap(arr, 0, i);
//交换之后, 需要重新检查堆是否符合大顶堆, 不符合则要调整
heapAdjust(arr, 0, i);
}
return arr;
}
/** 构建大顶堆 */
private static void heapAdjust(int[] arr, int i, int n) {
int childLeaf;
int fatherLeaf;
for (fatherLeaf = arr[i]; leftLeafChild(i) < n; i = childLeaf) {
childLeaf = leftLeafChild(i);
//如果左子树小于右子树, 则需要比较右子树和父节点
if (childLeaf != n - 1 && arr[childLeaf] < arr[childLeaf + 1]) {
//序号增1, 指向右子树
childLeaf++;
}
//父节点小于孩子结点时, 进行交换
if (fatherLeaf < arr[childLeaf]) {
arr[i] = arr[childLeaf];
} else {
//大顶堆结构未被破坏, 不需要调整
break;
}
}
arr[i] = fatherLeaf;
}
// 获取到左子结点
private static int leftLeafChild(int i) {
return 2 * i + 1;
}
private static void swap(int[] arr, int index1, int index2) {
int tmp = arr[index1];
arr[index1] = arr[index2];
arr[index2] = tmp;
}7.归并排序
/**
* 递归将一个较大的数组不断切分为较小的两个子数组, 直到无法再切分之后再做合并, 并在合并的过程中调整顺序
* 归并算法的难点是如何尽可能的减少额外存储空间的使用
*/
public static int[] mergeSort(int[] arr) {
if (arr == null || arr.length == 0) {
return arr;
}
//finalArr 作为辅助数组
int[] finalArr = new int[arr.length];
inMergeSort(arr, finalArr, 0, arr.length - 1);
return finalArr;
}
private static void inMergeSort(int[] arr1, int[] arr2, int low, int high) {
if (high <= low) {
return;
}
int middle = (low + high) / 2;
//对左右子数组进行划分处理
inMergeSort(arr1, arr2, low, middle);
inMergeSort(arr1, arr2, middle + 1, high);
//最终合并两个有序的子数组
finalMergeSort(arr1, arr2, low, middle, high);
}
private static void finalMergeSort(int[] arr1, int[] arr2, int low, int middle, int high) {
int i = low;
int j = middle + 1;
int k = 0;
while (i <= middle && j <= high) {
if (arr1[i] <= arr1[j]) {
arr2[k++] = arr1[i++];
} else {
arr2[k++] = arr1[j++];
}
}
while (i <= middle) {
arr2[k++] = arr1[i++];
}
while (j <= high) {
arr2[k++] = arr1[j++];
}
for (i = 0; i < k; ++i) {
arr1[low + i] = arr2[i];
}
}近期文章：