[关闭]
@TryLoveCatch 2021-07-08T11:06:42.000000Z 字数 3718 阅读 1120

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/

排序

查找

实战

其他

二分查找

你真的会写二分查找吗

  1. /**
  2. * 二分查找,找到该值在数组中的下标,否则为-1
  3. */
  4. static int binarySerach(int[] array, int key) {
  5. int left = 0;
  6. int right = array.length - 1;
  7. // 这里必须是 <=
  8. while (left <= right) {
  9. int mid = (left + right) / 2;
  10. if (array[mid] == key) {
  11. return mid;
  12. }
  13. else if (array[mid] < key) {
  14. left = mid + 1;
  15. }
  16. else {
  17. right = mid - 1;
  18. }
  19. }
  20. return -1;
  21. }

合并两个有序数组

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

反转数组

Java实现数组的反转

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

  1. package javase.base;
  2. import java.util.Arrays;
  3. /**
  4. * 数组的反转
  5. * User: Realfighter
  6. * Date: 2014/9/22
  7. * Time: 21:53
  8. */
  9. public class ArrayReverse {
  10. public static void main(String[] args) {
  11. int[] array = {1, 2, 3, 4, 5};
  12. System.out.println(Arrays.toString(reverse1(array)));
  13. System.out.println(Arrays.toString(reverse2(array)));
  14. }
  15. /**
  16. * 没有考虑效率的反转
  17. *
  18. * @param array
  19. * @return
  20. */
  21. private static int[] reverse1(int[] array) {
  22. int[] newArray = new int[array.length];
  23. for (int i = 0; i < array.length; i++) {
  24. newArray[i] = array[array.length - 1 - i];
  25. }
  26. return newArray;
  27. }
  28. /**
  29. * 考虑时间复杂度和空间复杂度的反转
  30. *
  31. * @param array
  32. * @return
  33. */
  34. private static int[] reverse2(int[] array) {
  35. int temp;
  36. for (int i = 0; i < array.length / 2; i++) {
  37. temp = array[i];
  38. array[i] = array[array.length - 1 - i];
  39. array[array.length - 1 - i] = temp;
  40. }
  41. return array;
  42. }
  43. }

荷兰国旗

算法笔记_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指针就不能动。

  1. package com.liuzhen.array_2;
  2. public class HollandFlagProblem {
  3. //输出荷兰国旗问题后的排序结果,时间复杂度为O(n),空间复杂度为O(1)
  4. public void getHollandSort(int[] A){
  5. int begin = 0;
  6. int current = 0;
  7. int end = A.length - 1;
  8. while(current <= end){
  9. //值得注意的是:此处if语句是使用if-else if-else if,而没有使用if-if-if。这样使用保证每一次循环只执行一个条件,
  10. //否则,若使用if-if-if,可能会形成一次循环执行两到三个if条件,造成最终结果错误(PS:即在循环结束前,发生current > end)
  11. if(A[current] == 0){
  12. swap(A,begin,current);
  13. begin++;
  14. current++;
  15. }
  16. else if(A[current] == 1)
  17. current++;
  18. else if(A[current] == 2){
  19. swap(A,current,end);
  20. end--;
  21. }
  22. }
  23. //输出排完序后的数组A相应元素
  24. System.out.println("对数组A进行划分后的元素顺序为:");
  25. for(int i = 0;i < A.length;i++)
  26. System.out.print(A[i]+" ");
  27. }
  28. //交换数组A中m位置和n位置上元素的值
  29. public void swap(int[] A,int m,int n){
  30. int temp = A[m];
  31. A[m] = A[n];
  32. A[n] = temp;
  33. }
  34. public static void main(String[] args){
  35. HollandFlagProblem test = new HollandFlagProblem();
  36. 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};
  37. test.getHollandSort(A);
  38. }
  39. }

参考

数据结构与算法系列 目录

排序

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

时间复杂度

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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注