Java基础之数据结构与算法

java java基础 算法 数据结构

数据结构

数组

数组有上界和下界，数组的元素在上下界内是连续的。
数组的特点：

• 插入快
• 查找慢
  如果根据下标来查找是很快的。但是通常我们都是根据元素值来查找，给定一个元素值，然后需要遍历数组。
• 删除慢
  删除之后，需要整体前移
• 大小固定

链表

JAVA中关于链表的操作和基本算法
单链表
双端链表
双向链表

栈

队列

哈希表

二叉树

JAVA下实现二叉树的先序、中序、后序、层序遍历（递归和循环）

算法

时间复杂度

https://www.iamshuaidi.com/591.html

递归

https://www.iamshuaidi.com/272.html

LeetCode

https://www.zhihu.com/question/36738189/answer/95751126
https://www.zhihu.com/question/36738189/answer/864005192

https://leetcode-cn.com/problemset/all/
https://leetcode-cn.com/problemset/leetcode-hot-100/

排序

查找

实战

其他

• 两个栈实现队列，两个队列实现栈
  https://www.cnblogs.com/kaituorensheng/archive/2013/03/02/2939690.html

• xx

二分查找

你真的会写二分查找吗

/**
 * 二分查找，找到该值在数组中的下标，否则为-1
 */
static int binarySerach(int[] array, int key) {
    int left = 0;
    int right = array.length - 1;
    // 这里必须是 <=
    while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }
    return -1;
}

合并两个有序数组

public class MyClass {
    public static void main(String[] args) {
        int[] num1 = new int[]{1, 2, 4, 6, 7, 123, 411, 5334, 1414141, 1314141414};
        int[] num2 = new int[]{0, 2, 5, 7, 89, 113, 5623, 6353, 134134};
        //变量用于存储两个集合应该被比较的索引（存入新集合就加一）
        int a = 0;
        int b = 0;
        int[] num3 = new int[num1.length + num2.length];
        for (int i = 0; i < num3.length; i++) {
            if (a < num1.length && b < num2.length) {   //两数组都未遍历完，相互比较后加入
                if (num1[a] > num2[b]) {
                    num3[i] = num2[b];
                    b++;
                } else {
                    num3[i] = num1[a];
                    a++;
                }
            } else if (a < num1.length) {   //num2已经遍历完，无需比较，直接将剩余num1加入
                num3[i] = num1[a];
                a++;
            } else if (b < num2.length) {    //num1已经遍历完，无需比较，直接将剩余num2加入
                num3[i] = num2[b];
                b++;
            }
        }
        System.out.println("排序后:" + Arrays.toString(num3));
    }
}

反转数组

Java实现数组的反转

我们首先想到的一般就是对整个数组进行遍历，然后通过空的数组来反向的存储指定数组的元素，我们假定数组的长度为n，这样我们一次反转就需要循环n次，当 n足够大时，效率可想而知，那么有没有更有效率的方法呢，其实我们只需要简单的把数组的第1位与第n位交换，第2位与第n-1位交换，依次类推，我们只需 要循环n/2次即可，简单代码如下：

package javase.base;
import java.util.Arrays;
/**
 * 数组的反转
 * User: Realfighter
 * Date: 2014/9/22
 * Time: 21:53
 */
public class ArrayReverse {
    public static void main(String[] args) {
        int[] array = {1, 2, 3, 4, 5};
        System.out.println(Arrays.toString(reverse1(array)));
        System.out.println(Arrays.toString(reverse2(array)));
    }
    /**
     * 没有考虑效率的反转
     *
     * @param array
     * @return
     */
    private static int[] reverse1(int[] array) {
        int[] newArray = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            newArray[i] = array[array.length - 1 - i];
        }
        return newArray;
    }
    /**
     * 考虑时间复杂度和空间复杂度的反转
     *
     * @param array
     * @return
     */
    private static int[] reverse2(int[] array) {
        int temp;
        for (int i = 0; i < array.length / 2; i++) {
            temp = array[i];
            array[i] = array[array.length - 1 - i];
            array[array.length - 1 - i] = temp;
        }
        return array;
    }
}

荷兰国旗

算法笔记_051:荷兰国旗问题（Java）

现有n个红白蓝三种不同颜色的小球，乱序排列在一起，请编写算法，使得从左至右的球依次为红球、白球、蓝球

为了方便编码与讨论，用数字0表示红球，数字1表示白球，数字2表示蓝球，所以最后生成的排列为0,1,2。
解决该问题，只需先设定三个用于指定元素的下标指针（PS：在Java中没有指针，此处方便描述）:一个前指针begin，一个中指针current，一个后指针end。Current指针遍历整个数组序列：
（1）当current指针所指元素为0时，与begin指针所指的元素交换，而后current++，begin++；
（2）当current指针所指元素为1时，不做任何交换，而后current++；
（3）当current指针所指元素为2时，与end指针所指的元素交换，而后current指针不动，end--.
那么，为什么在上述第（3）步中，current指针不动？因为如果end所指元素为0时，此时current指针就不能动。

package com.liuzhen.array_2;
public class HollandFlagProblem {
    //输出荷兰国旗问题后的排序结果，时间复杂度为O(n)，空间复杂度为O(1)
    public void getHollandSort(int[] A){
        int begin = 0;
        int current = 0;
        int end = A.length - 1;
        while(current <= end){
            //值得注意的是：此处if语句是使用if-else if-else if，而没有使用if-if-if。这样使用保证每一次循环只执行一个条件，
            //否则，若使用if-if-if，可能会形成一次循环执行两到三个if条件，造成最终结果错误（PS:即在循环结束前，发生current > end）
            if(A[current] == 0){
                swap(A,begin,current);
                begin++;
                current++;
            }
            else if(A[current] == 1)
                current++;    
            else if(A[current] == 2){
                swap(A,current,end);
                end--;
            }
        }
        //输出排完序后的数组A相应元素
        System.out.println("对数组A进行划分后的元素顺序为：");
        for(int i = 0;i < A.length;i++)
            System.out.print(A[i]+" ");
    }
    //交换数组A中m位置和n位置上元素的值
    public void swap(int[] A,int m,int n){
        int temp = A[m];
        A[m] = A[n];
        A[n] = temp;
    }
    public static void main(String[] args){
        HollandFlagProblem test = new HollandFlagProblem();
        int[] A = {2,0,2,0,0,2,1,1,0,2,1,0,1,2,0,1,2,0,1,0,2,1,0,2,0,1,2,0,1,2,0,2,1,0};
        test.getHollandSort(A);
    }
}

参考

数据结构与算法系列 目录

排序

程序员必知的8大排序(三)-------冒泡排序，快速排序（java实现
八大排序算法实战：思想与实现
Java 八大排序实现

时间复杂度

时间复杂度 O(log n) 意味着什么？
算法时间复杂度计算