1.二分查找(递归与非递归实现)
基本算法,掌握好循环条件
package com.company;
/**
* Description :二分查找(递归与非递归实现)
* Created by Wanbo
* Date :2021/7/18
*/
public class offer1 {
// 非递归
public static int binarySearch(int []arr, int num){
int low =0, high = arr.length-1, mid = 0;
while (low <= high){
mid = (low + high)/2;
if(arr[mid] == num){
return mid;
}
else if(arr[mid] > num){
high = mid-1;
}
else if(arr[mid] < num){
low = mid+1;
}
}
return -1;
}
// 递归
public static int recursiveBinarySearch(int arr[], int low, int high, int num){
int mid = 0;
if(low <= high) {
mid = (low + high)/2;
if(arr[mid] == num){
return mid;
}
else if(arr[mid] > num){
return recursiveBinarySearch(arr, low, high-1, num);
}
else if(arr[mid] < num){
return recursiveBinarySearch(arr, mid+1, high, num);
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = {1,3,5,7,9,10,12,15,20};
System.out.println(binarySearch(arr,7));
System.out.println(recursiveBinarySearch(arr,0,arr.length-1,7));
}
}
2.二维数组中查找
两个for循环复杂度比较高,从右上或左下进行遍历查找,每遍历一次就能减少一行/列,降低复杂度
package com.company;
/**
* Description :二维数组中查找
* Created by Wanbo
* Date :2021/7/18
*/
public class offer2 {
// 右上或左下开始遍历,减少遍历范围,我采用右上
public static boolean findNumIn2DArray(int array[][], int num) {
if(array.length == 0 || array[0].length == 0){
return false;
}
int rows = array.length;
int columns = array[0].length;
int i = 0;
int j = columns - 1;
while(i < rows && j >=0) {
if(array[i][j] == num) {
return true;
}
else if(array[i][j] > num) {
j--;
}
else {
i++;
}
}
return false;
}
public static void main(String[] args) {
int arr[][] = {
{1,2,3},
{4,5,6},
{7,8,9}
};
System.out.println(findNumIn2DArray(arr, 2));
}
}
3.旋转数组中最小的数
旋转数组可以分为两个子数组,都是有序,且后面的子数组最大的要小于等于左边的子数组最小的元素,常规遍历复杂度为n,采用二分查找。
package com.company;
/**
* Description :旋转数组中最小的数
* Created by Wanbo
* Date :2021/7/18
*/
public class offer3 {
public static int minNumberInRotateArray(int [] array) {
if(array.length==0){
return 0;
}
int low = 0, high = array.length-1, mid = 0;
while(low < high){
if(array[low]<array[high]){
return array[low];
}
mid = (high+low)/2;
if(array[mid] > array[high]){
low = mid+1;
}else if(array[mid] < array[high])
{
high = mid;
}else{
//存在low high mid大小相同的情况,左移high,比较右边小的子数组
high --;
}
}
return array[low] ;
}
public static void main(String[] args) {
// int arr[] = {3,4,5,1,2};
int arr[] = {2,2,2,1,2};
System.out.println(minNumberInRotateArray(arr));
}
}
4.调整数组使得奇数在前偶数在后
类似快排,双指针i,j,指向两端,往中间遍历
i指向的为奇数跳过,j指向的为偶数跳过
i指向偶数,j指向奇数交换值
i=j时退出
package com.company;
import java.lang.reflect.Array;
import java.util.Arrays;
/**
* Description :调整数组使得奇数在前偶数在后
* Created by Wanbo
* Date :2021/7/18
*/
public class offer4 {
/*
* 类似快排,双指针i,j,指向两端,往中间遍历
* i指向的为奇数跳过,j指向的为偶数跳过
* i指向偶数,j指向奇数交换值
* i=j时退出
* */
public static int[] adjustOddAndEven(int arr[]){
int i = 0, j = arr.length-1, temp = 0;
while(i < j){
while(i<j && arr[i]%2 ==1){
i++;
}
while(i<j && arr[j]%2 == 0){
j--;
}
if(i < j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
return arr;
}
public static void main(String[] args) {
int arr[] = {1,2,3,4,5,6,7};
System.out.println(Arrays.toString(adjustOddAndEven(arr)));
}
}
5.顺时针打印矩阵
找到打印规律,注意起始与终止的循环下标,添加到list中进行打印。
package com.company;
import java.util.ArrayList;
/**
* Description :顺时针打印矩阵
* Created by Wanbo
* Date :2021/7/18
*/
public class offer5 {
public static ArrayList<Integer> getList(int arr[][]) {
ArrayList<Integer> list=new ArrayList<>();
int row=arr.length, col=arr[0].length;
if(arr.length == 0 || row<0 || col<0){
return null;
}
int count=0;
while(col>count*2 && row>count*2){
getNum(list,arr,col,row,count);
count++;
}
return list;
}
public static void getNum(ArrayList<Integer> list, int [][] arr,int col,int row,int start){
int endrow=row-start-1;
int endcol=col-start-1;
//从左到右打印一行,行号为count,列号为count到endrow递增,添加row个数
for(int i=start;i<=endcol;i++){
list.add(arr[start][i]);
}
//从上往下打印,终止行号需大于起始行号,行号为count+1到endrow递增,添加col-1个数
if(endrow>start){
for(int i=start+1;i<=endrow;i++){
list.add(arr[i][endcol]);
}
}
//从右往左打印,终止列号要大于起始列号,添加row-1个数
// 列号为endcol-1到count递减
if(endrow>start && endcol>start){
for(int i=endcol-1;i>=start;i--){
list.add(arr[endrow][i]);
}
}
//从下往上打印,终止行号至少比开始行号大1,行号为endrow-1到count+1递减,添加col-2个数
if((endrow-start>1)&&endcol>start){
for(int i=endrow-1;i>=start+1;i--){
list.add(arr[i][start]);
}
}
}
public static void main(String[] args) {
int arr[][] = {
{1,2,3,4},
{4,5,6,5},
{7,8,9,6}
};
ArrayList<Integer> list = getList(arr);
System.out.println(list.toString());
}
}
6.数组中超过一半的数
排序找中位数,即使出现次数最多的数,根据数据规模,特征选择合适的排序算法,详见常见八大排序算法
package com.company;
/**
* Description :数组中超过一半的数
* Created by Wanbo
* Date :2021/7/20
*/
public class offer6 {
// 排序找中位数,即使出现次数最多的数,用快排
public static int getNum(int arr[]){
rotate(arr,0,arr.length-1);
return arr[arr.length/2];
}
public static int quickSort(int[] arr, int low, int high) {
int i = low, j = high, temp = arr[low];
while (i < j) {
while (i < j && arr[j] >= temp) {
j--;
}
if (i < j) {
arr[i] = arr[j];
}
while (i < j && arr[i] <= temp) {
i++;
}
if (i < j) {
arr[j] = arr[i];
}
}
arr[i] = temp;
return i;
}
public static void rotate(int[] arr,int low, int high){
if(arr == null || arr.length == 0){
return;
}
if(low < high) {
int pos = quickSort(arr, low, high);
quickSort(arr, low, pos - 1);
quickSort(arr, pos + 1, high);
}
}
public static void main(String[] args) {
int arr[] = {3,4,6,1,4,5,2,2,2,2,2,2};
System.out.println(getNum(arr));
}
}
7.统计一个数字在排序数组中出现的次数
for一次循环每次遇见key次数+1,复杂度为n,可以采用二分查找,找出数组中第一次与最后一次出现数字的位置,它们的差+1就是出现的次数,复杂度为logn
package com.company;
/**
* Description :统计一个数字在排序数组中出现的次数
* Created by Wanbo
* Date :2021/7/20
*/
public class offer7 {
public static int getNumOfCount(int arr[], int key){
if(arr.length == 0 || arr == null){
return 0;
}
int firstKey = 0, lastK = 0, count = 0;
firstKey = getFirstK(arr, key);
lastK = getLastK(arr, key);
if(firstKey != -1 && lastK != -1){
return (lastK-firstKey+1);
}
return 0;
}
public static int getFirstK(int arr[], int key){
int low = 0, high = arr.length-1, mid = 0;
while(low <= high){
mid = (low+high)>>1;
if(arr[mid] == key){
if(arr[mid-1] < key){
return mid;
}else {
high = mid-1;
}
}else if(arr[mid] < key){
low = mid+1;
}else {
high = mid-1;
}
}
return -1;
}
public static int getLastK(int arr[], int key){
int low = 0, high = arr.length-1, mid = 0;
while(low <= high){
mid = (low+high)>>1;
if(arr[mid] == key){
if(arr[mid+1] > key){
return mid;
}else {
low = mid+1;
}
}else if(arr[mid] < key){
low = mid+1;
}else {
high = mid-1;
}
}
return -1;
}
public static void main(String[] args) {
int arr[] = {1,2,3,3,4,4,4,4,4,5,6};
System.out.println(getNumOfCount(arr,4));
System.out.println();
}
}
8.求数组中最小的K个数
排序,输出前k个,用一下堆排
package com.company;
/**
* Description :
* Created by Wanbo
* Date :2021/7/20
*/
public class offer8 {
public static void adjust(int[] arr, int start, int end){
//start表示要调整树的根节点
int tmp = arr[start];
//找左右 孩子的最大值
for(int i=2*start+1; i<=end; i=2*i+1){
//判断是否有右孩子
if(i+1 <= end && arr[i] < arr[i+1]){
i++;//i指向左右孩子的最大值
}
if(arr[i] > tmp){
//需要将arr[i]换到start位置
arr[start] = arr[i];
start = i; //更新start,保存当前最大孩子的下标
}else{
break;
}
}
arr[start] = tmp;
}
public static void headSort(int[] arr){
if(arr == null || arr.length == 0){
return;
}
//i初始化为最后一个叶子节点所在子树的根节点
//经过for循环之后发现当前序列所对应的堆是大根堆
for(int i=(arr.length-1-1)/2; i>=0 ;i--){
adjust(arr, i, arr.length-1);
}
for(int i=0; i<arr.length; i++){
//相当于将根节点(待排序列的最大值)换到待排序列的最后
int tmp = arr[0];
arr[0] = arr[arr.length-1-i];
arr[arr.length-1-i] = tmp;
adjust(arr, 0, arr.length-1-i-1);
}
}
public static void main(String[] args) {
int[] arr = {2, 9, 10, 11, 29, 3, 6, 100, 50, 67, 30, 8};
int k = 5;
headSort(arr);
for (int i=0; i<k; i++) {
System.out.println(arr[i]);
}
}
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)