常见算法（十一）

查找算法

基本查找

从数组中一个一个去找数据。

范例：

//需求:定义一个方法利用基本查找，查询某个元素在数组中的索引，包括元素重复的
//数据如下：{88,88,99,44,88,88,1234}
import java.util.ArrayList;
public class Test{
    public static void main(String[] args){
        int[] arr={88,88,99,44,88,88,1234};
        int num=88;
        ArrayList<Integer> list=find(arr,num);
        for(int i=0;i<list.size();i++){
            System.out.println(list.get(i));
        }
    }
    public static ArrayList<Integer> find(int[] arr, int num){
        ArrayList<Integer> list=new ArrayList<>();
        for(int i=0;i<arr.length;i++){
            if(arr[i]==num) {
                list.add(i);
            }
        }
        return list;
    }
}

二分查找

前提条件：数组中的数据是必须有序的。

核心逻辑：每次排除一般的查找范围。

范例

//需求:定义一个方法利用二分查找,查询某个元素在数组中的索引
//数据如下：{16,48,78,88,91,96,105,144,151}
public class Test{
    public static void main(String[] args){
        int arr[]={16,48,78,88,91,96,105,144,151};//该数组从小到大排序
        int num=48;
        int result=find(arr,num);
        if(result==-1){
            System.out.println("并无此数字");
        }else{
            System.out.println(result);
        }
    }
    public static int find(int arr[],int num){
    	//1.定义查找范围
        int left=0;//数组首位
        int right=arr.length-1;//数组末尾
        //利用循环不断查找数据
        while(true){
            if(left>right){
                return -1;
            }
            //找到left和right的中间位置并放入mid
            int mid=(left+right)/2;
            //用mid指向的元素和num比较
            if(arr[mid]>num) {
            	//num在mid下标的左边
                right = mid - 1;
            }else if(arr[mid]<num){
                //num在mid下标的右边
                left=mid+1;
            }else{
            	//num和mid指向的元素一样
                return mid;
            }
        }
    }
}
/*
1
*/

插值查找

基于二分查找的基础上，使mid更靠近想要查找的元素。

mid=left+(key-arr[left])/(arr[right]-arr[left])*(right-left)

注：要求数据尽可能的分布均匀，若不均匀，插值查找反而会降低效率。

代码与二分查找类似，只需修改mid的计算方式。

根据黄金分割点来计算mid指向的位置。

斐波那契查找

分块查找

分块查找适用于数据较多，但是数据不会发生变化的情况。

分块原则：

1. 前一块中的最大数据，小于后一块的所有数据（块内无序，快间有序）
2. 块数量一般是数字个数的开根号，16个数组一般为4块左右

核心思路：先确定块，再在块中挨个寻找。

范例：

/*
实现步骤：
1.创建数组blocks存放每一个块对象的信息
2.先查找blocks确定要查找的数据属于哪一块
3.再单独遍历这一块数据即可
*/
//Test类
public class Test{
    public static void main(String[] args){
        int[] arr = {16, 5, 9, 12,21, 18,
                    32, 23, 37, 26, 45, 34,
                    50, 48, 61, 52, 73, 66};
        //创建三个块对象，并放入数组
        Block block1=new Block(21,0,5);
        Block block2=new Block(45,6,11);
        Block block3=new Block(73,12,17);
        Block[] blocks={block1,block2,block3};
        //要查找的元素
        int num=26;
        //调用方法，开始查找，若数组中存在要查找的元素返回索引，若无，返回-1
        int index=getIndex(blocks,num,arr);
        if(index==-1){
            System.out.println("无");
        }else{
            System.out.println(index);
        }

    }
    //寻找num索引
    public static int getIndex(Block[] blocks,int num,int arr[]){
        //确定number是在那一块当中，弱不存在返回-1
        int b=getBlockIndex(blocks,num);
        if(b==-1){
            return -1;
        }
        //获取该块起始索引和结束索引
        int start=blocks[b].getStartIndex();
        int end=blocks[b].getEndIndex();
        for(int i=start;i<=end;i++){
            if(num==arr[i]){
                return i;
            }
        }
        return -1;
    }

    //判断num在哪一块
    public static int getBlockIndex(Block[] blocks,int num){
        //从0索引开始遍历blocks，如果num小于max，num便这一块当中的
        for(int i=0;i<blocks.length;i++){
            if(num<=blocks[i].getMax()){
                return i;
            }
        }
        return -1;
    }
}
//Block.java
public class Block {
    private int max;
    private int startIndex;
    private int endIndex;
    public Block(){}
    public Block(int max, int startIndex, int endIndex) {
        this.max = max;
        this.startIndex = startIndex;
        this.endIndex = endIndex;
    }

    public int getMax() {
        return max;
    }

    public void setMax(int max) {
        this.max = max;
    }

    public int getStartIndex() {
        return startIndex;
    }

    public void setStartIndex(int startIndex) {
        this.startIndex = startIndex;
    }

    public int getEndIndex() {
        return endIndex;
    }

    public void setEndIndex(int endIndex) {
        this.endIndex = endIndex;
    }
}

排序算法

冒泡排序

1. 相邻的元素两两比较，若是从小到大排，大的放右边，小的放左边；若是从大到小排，小的放右边，大的放左边。
2. 第一轮比较完毕之后，最大值（最小值）就已经确定，第二轮可以少循环一次，后面以此类推
3. 如果数组中有n个数据，总共我们只要执行n-1轮的代码就可以

范例：

public class Test{
    public static void main(String[] args){
        int[] arr = {16, 5, 9, 12,21, 18};
        for(int i=0;i<arr.length-1;i++){
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int t=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=t;
                }
            }
        }
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}
/*
5 9 12 16 18 21 
*/

选择排序

1. 从0索引开始，跟后面的元素一一比较
2. 若是从小到大排，小的放前面，大的放后面；若是从大到小排，大的放前面，小的放后面
3. 第一次循环结束后，最小（大）的数据已经确定
4. 第二次循环从1索引开始以此类推
5. 第三轮循环从2索引开始以此类推
6. 第四轮循环从3索引开始以此类推。

范例：

public class Test{
    public static void main(String[] args){
        int[] arr = {16, 5, 9, 12,21, 18};
        for(int i=0;i<arr.length-1;i++){
            for(int j=i+1;j<arr.length;j++){
                if(arr[i]>arr[j]){
                    int t=arr[i];
                    arr[i]=arr[j];
                    arr[j]=t;
                }
            }
        }
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

插入排序

将0到N索引的元素看做是有序的，把N+1索引的元素到最后一个当成是无序的。

遍历无序的数据，将遍历到的元素插入有序序列中适当的位置，如遇到相同数据，插在后面。

N的范围：0~最大索引

范例：

public class Test{
    public static void main(String[] args){
        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
        int startIndex=-1;
        for(int i=0;i<arr.length;i++){
            if(arr[i]>arr[i+1]){
                startIndex=i+1;
                break;
            }
        }
        for(int i=startIndex;i<arr.length;i++){
            int j=i;
            while(j>0 && arr[j-1]>arr[j]){
                int t=arr[j-1];
                arr[j-1]=arr[j];
                arr[j]=t;
                j--;
            }
        }
        for (int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
}

快速排序

1. 在数组中挑出一个元素，一般是左边第一个数字，称为 “基准数”;
2. 创建两个指针，一个从前往后走，一个从后往前走。
3. 先执行后面的指针，找出第一个比基准数小的数字
4. 再执行前面的指针，找出第一个比基准数大的数字
5. 交换两个指针指向的数字
6. 直到两个指针相遇
7. 将基准数跟指针指向位置的数字交换位置，称之为：基准数归位。
8. 第一轮结束之后，基准数左边的数字都是比基准数小的，基准数右边的数字都是比基准数大的。
9. 把基准数左边看做一个序列，把基准数右边看做一个序列，按照刚刚的规则递归排序

范例：

package com.ljsblog.domain12;
public class Test{
    public static void main(String[] args){
        int[] arr={24,78,14,67,12,74,45,57,135,78,46};
        p(arr,0,arr.length-1);
        for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]+" ");
        }
    }
    public static void p(int[] arr,int i,int j){
        int start=i;
        int end=j;
        if(start>end){
            return;
        }
        int base=arr[i];
        while(start!=end){
            while(true){
                if(start>=end || base>arr[end]){
                    break;
                }
                end--;
            }while(true){
                if(start>=end || base<arr[start]){
                    break;
                }
                start++;
            }
            int t=arr[start];
            arr[start]=arr[end];
            arr[end]=t;
        }
        int t=arr[i];
        arr[i]=arr[start];
        arr[start]=t;
        p(arr,i,start-1);
        p(arr,start+1,j);
    }
}

Arrays

操作数组的工具类。

常用方法

toString

格式：

public static String toString(数组)

说明：把数组拼接成一个字符串

binarySearch

格式：

public static int binarySearch(数组,查找的元素)

说明：二分查找法查找元素。

注：

二分查找的前提是数组中元素必须有有序的。

若使用binarySearch方法，数组中的元素必须是升序的。

若要查找的元素不存在，则返回插入点的负数再减一。

copyOf

格式：

public static int[] copyOf(原数组,新数组长度)

说明：拷贝数组

注：

1. 若新数组长度小于原数组长度，会部分拷贝
2. 若新数组长度等于原数组长度，会完全拷贝
3. 若新数组长度大于原数组长度，会完全拷贝，剩下的元素默认初始化。

copyOfRange

格式：

public static int[] copyOfRange(原数组,起始索引,结束索引)

说明：拷贝数据，指定范围，包头不包尾

fill

格式：

public static void fill(数组,元素)

说明：填充数组

sort

格式1：

public static void sort(数组)

说明：默认情况下，给基本数据类型进行升序排列，底层使用的是快速排序。

格式2：

public static void sort(数组,排序规则)

说明：

只能给引用数据类型的数组进行排序，若数组是基本数据类型，需转换成对应的包装类。

第二个参数是一个接口，所以我们在调用方法时，需传递这个接口的实现对象，作为排序的规则。

此实现类一般只需使用一次，可以直接采取匿名内部类的方式。

底层原理：

利用插入排序+二分查找的方式进行排序。

默认把0索引的数据当做有序的序列，1所以到最后为无序序列，遍历无序的序列得到其中每一个元素。

设当前遍历所得元素为X元素，把X往有序序列插入，利用二分查找确定X元素的插入点，令X元素和插入点元素比较，比较的规则就是compare方法的方法体。

若方法返回值为负数，则X继续与前面的数据比较。

若方法返回值为正数，则X继续与后面的数据比较。

若返回值为0，则X与后面的元素比较。

直到确定X的最终位置为止。

compare方法的形参：

参数一：o1,表示在无序序列中，遍历得到的每一个元素。

参数二：o2,表示有序序列的元素。

返回值：

负数，表示X是小的，放在前面；正数，表示X是大的，放在后面；0，表示当前要插入的元素跟现在的元素是一样的，放在后面。

结论：

• o1-o2，升序排列
• o2-o2，降序排列

范例

import java.util.Arrays;
import java.util.Comparator;

public class Test{
    public static void main(String[] args){
        System.out.println("toString方法");
        int[] arr1={1,2,3,4,5,6,7,8,9};
        String str1= Arrays.toString(arr1);
        System.out.println(str1);
        System.out.println();

        System.out.println("binarySearch方法");
        System.out.println(Arrays.binarySearch(arr1,3));
        System.out.println(Arrays.binarySearch(arr1,9));
        System.out.println(Arrays.binarySearch(arr1,10));
        System.out.println();

        System.out.println("copyOf方法");
        int[] arr2=Arrays.copyOf(arr1,9);
        String str2=Arrays.toString(arr2);
        System.out.println(str2);
        int[] arr3=Arrays.copyOf(arr1,5);
        String str3=Arrays.toString(arr3);
        System.out.println(str3);
        int[] arr4=Arrays.copyOf(arr1,20);
        String str4=Arrays.toString(arr4);
        System.out.println(str4);
        System.out.println();

        System.out.println("copyOfRange方法");
        int[] arr5=Arrays.copyOfRange(arr1,0,5);
        String str5=Arrays.toString(arr5);
        System.out.println(str5);
        System.out.println();

        System.out.println("fill方法");
        Arrays.fill(arr5,1);
        System.out.println(Arrays.toString(arr5));
        System.out.println();

        System.out.println("sort格式1");
        int[] arr6={14,87,124,57,45,75,12,78,33};
        Arrays.sort(arr6);
        String str6=Arrays.toString(arr6);
        System.out.println(str6);

        System.out.println("sort格式2");
        Integer[] arr7={14,87,124,57,45,75,12,78,33};
        Arrays.sort(arr7,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        String str7=Arrays.toString(arr7);
        System.out.println(str7);
    }
}

Lambda表达式

Lambda表达式是JDK8开始后出现的一种新语法形式。

格式：

()->{

}
//() 对应方法的形参
//-> 固定格式
//{} 对应着方法的方法体

基本作用：简化函数化接口的匿名内部类的写法。

函数化接口：有且仅有一个抽象方法的接口叫做函数化接口，接口上方可以加@FunctionalInterface注解。

使用前提：必须是接口的匿名内部类，接口中只能有一个抽象方法。

好处:Lambda是一个匿名函数，可以把Lambda表达式理解为一段可以传递的代码，它可以写成更简洁，更灵活的代码。

省略写法

省略核心：可推导，可省略。

• 参数类型可省略
• 若只有一个参数，参数类型和()均可省
• 若Lambda表达式的方法体只有一行，大括号，分号，return均可省略，但必须同时省略。

对比范例一

import java.util.Arrays;
import java.util.Comparator;
public class Test{
    public static void main(String[] args){
        Integer[] arr1={69,42,65,89,26,32,16};
        //原版
        Arrays.sort(arr1,new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o1-o2;
            }

        });
        System.out.println(Arrays.toString(arr1));


        //Lambda表达式
        Integer[] arr2={69,42,65,89,26,32,16};
        Arrays.sort(arr2,(Integer o1,Integer o2)->{
            return o1-o2;
        });
        System.out.println(Arrays.toString(arr2));

        //Lambda表达式省略版
        Integer[] arr3={69,42,65,89,26,32,16};
        Arrays.sort(arr3,(o1,o2)->o1-o2);
        System.out.println(Arrays.toString(arr3));
    }
}
/*
[16, 26, 32, 42, 65, 69, 89]
[16, 26, 32, 42, 65, 69, 89]
[16, 26, 32, 42, 65, 69, 89]
*/

对比范例二

public class Test{
    public static void main(String[] args){
        //原版
        method("小白",new Swim(){
            @Override
            public void swiming(String name){
                System.out.println(name+"游泳");
            }
        });

        //Lambda表达式
        method("小白",(String name)->{
            System.out.println(name+"游泳");
        });

        //Lambda表达式省略版
        method("小白",name->System.out.println(name+"游泳"));
    }
    public static void method(String name,Swim s){
        s.swiming(name);
    }
}
@FunctionalInterface
interface Swim{
    public abstract void swiming(String name);
}
/*
小白游泳
小白游泳
小白游泳
*/

范例

/*
定义数组并存储一些字符串，利用Arrays中的sort方法进行排序
要求：
	按照字符串中的长度排序，从短到长。
*/
import java.util.Arrays;
import java.util.Comparator;
public class Test{
    public static void main(String[] args) {
        String[] arr={"aaaa","a","aaaaa","aaa","aaaaaaaaaaa"};
        //原版
        /*
        Arrays.sort(arr,new Comparator<String>(){
            @Override
            public int compare(String o1, String o2) {
                return o1.length()-o2.length();
            }
        });
        */
        //Lambda版
        /*
        Arrays.sort(arr,(String o1,String o2)->{
            return o1.length()-o2.length();
        });
        */
        //Lambda省略版
        Arrays.sort(arr,(o1,o2)->o1.length()-o2.length());
        System.out.println(Arrays.toString(arr));
    }
}
/*
[a, aaa, aaaa, aaaaa, aaaaaaaaaaa]
*/

算法题

例1

/*
定义数组并存储一些女朋友对象，利用Arrays的sort方法进行排序
要求1：属性有姓名，年龄，身高
要求2：按照年龄的大小进行排序，若年龄一致，按身高排序，若身高一致，按姓名的字母排序
*/
//Test.java
import java.util.Arrays;
import java.util.Scanner;
public class Test{
    public static void main(String[] args) {
        System.out.print("请输入你有几个女朋友：");
        Scanner scanner=new Scanner(System.in);
        int num=Integer.parseInt(scanner.nextLine());
        Girlfriend[] girlfriends=new Girlfriend[num];
        for(int i=0;i<num;i++){
            System.out.println("第"+(i+1)+"个");
            System.out.print("请输入姓名：");
            String name=scanner.nextLine();
            System.out.print("请输入年龄：");
            int age=Integer.parseInt(scanner.nextLine());
            System.out.print("请输入身高：");
            int height=Integer.parseInt(scanner.nextLine());
            Girlfriend girlfriend=new Girlfriend(age,height,name);
            girlfriends[i]=girlfriend;
        }
        Arrays.sort(girlfriends,(o1, o2)->{
                if(o1.getAge()!=o2.getAge()){
                    return o1.getAge()-o2.getAge();
                }else if(o1.getHeight()!=o2.getHeight()){
                    return o1.getHeight()-o2.getHeight();
                }else{
                    return o1.getName().compareTo(o2.getName());
                }
            }
        );
        System.out.println(Arrays.toString(girlfriends));
    }
}

//GirlFriend.java
public class Girlfriend {
    private int age;
    private int height;
    private String name;
    public Girlfriend(){}
    public Girlfriend(int age, int height, String name) {
        this.age = age;
        this.height = height;
        this.name = name;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public int getHeight() {
        return height;
    }

    public void setHeight(int height) {
        this.height = height;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }
    @Override
    public String toString() {
        return "Girlfriend{" +
                "age=" + age +
                ", height=" + height +
                ", name='" + name + '\'' +
                '}';
    }
}

例2

/*
有一对兔子，从出生后第三个月起每个月都会生一对兔子，小兔子长到第三个月起每月又生一对兔子，假如兔子不死，到第12个月共有几对兔子
*/
public class Test{
    public static void main(String[] args) {
        //方法一
        int[] arr=new int[12];
        arr[0]=1;
        arr[1]=1;
        for(int i=2;i<12;i++){
            arr[i]=arr[i-1]+arr[i-2];
        }
        System.out.println("第十二个月为"+arr[11]+"对兔子");
        System.out.println("第十二个月为"+Fn(12)+"对兔子");
    }
    //方法二
    public static int Fn(int num){
        if(num==1||num==2){
            return 1;
        }else{
            return Fn(num-1)+Fn(num-2);
        }
    }
}
/*
第十二个月为144对兔子
第十二个月为144对兔子
*/

例3

/*
有一堆桃子，猴子第一天吃其中一半，并多吃一个。以后每天猴子都吃当前剩下一半，再多吃一个，第10天的时候发现只剩一个桃子，最初总共多少桃子？
*/
public class Test{
    public static void main(String[] args){
        System.out.println(peach(1));
    }
    public static int peach(int num){
        if(num==10){
            return 1;
        }
        return (peach(num+1)+1)*2;
    }
}
/*
1534

*/