Java中数组的实际经典案例

2023-04-15 132

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： Java中数组的实际经典案例

数组不仅是Java中学习的重点，也是数据结构与算法中学习的重点，我们不仅要熟悉它，也要懂得运用它。

1. 数组的拷贝

数组的拷贝分为两种，一种是对值得拷贝，一种是对地址的拷贝。

上一章中我们已经知道了数组是储存在堆上的，在栈上new出来的只是一个局部变量，用于储存堆山的地址。

上代码：

import java.util.Arrays;
public class demo {
    public static int[] copyArray(int[] arr){
        int[] copyArr = arr;
        return copyArr;
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        System.out.println(Arrays.toString(copyArray(arr)));
    }
}

两个变量同时存储同一个地址。

import java.util.Arrays;
public class demo {
    public static int[] copyArray(int[] arr){
        int[] copyArr = new int[arr.length];
        copyArr = arr;
        return copyArr;
    }
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        System.out.println(Arrays.toString(copyArray(arr)));
    }
}

总结：只要是new出来的都是一个新地址。

2.查找数组中指定元素(二分查找)

针对有序数组, 可以使用更高效的二分查找

啥叫有序数组?

有序分为 " 升序 " 和 " 降序 "

如 1 2 3 4 , 依次递增即为升序 .

如 4 3 2 1 , 依次递减即为降序

那么顺序查找可不可以呢？

当然是可行的，但是如果数组非常大，我们需要找的值在后面，那就会造成速度非常慢，效果非常差。

那可以选择用二分查找（也可以选择其他更快更有效的算法）。

思路分析：

以升序数组为例, 二分查找的思路是先取中间位置的元素, 然后使用待查找元素与数组中间元素进行比较：

如果相等，即找到了返回该元素在数组中的下标

如果小于，以类似方式到数组左半侧查找

如果大于，以类似方式到数组右半侧查找

图解：

假设我们需要找5这个元素。

第一次查找：发现mid指向的值小于我们目的元素，letf就指向mid，right不移动，mid重新计算。

第二次查找：发现mid指向的值任然小于我们目的元素，letf就指向mid，right不移动，mid重新计算。

第三次查找：依旧和前两次查找一样。

直到找到这个目标元素。

public class demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        System.out.println(binarySearch(arr, 6));
    }
    public static int binarySearch(int[] arr, int toFind) {
        int left = 0;
        int right = arr.length - 1;
        while (left <= right) {
            int mid = (left + right) / 2;
            if (toFind < arr[mid]) {
              // 去左侧区间找
                right = mid - 1;
            } else if (toFind > arr[mid]) {
                // 去右侧区间找
                left = mid + 1;
            } else {
                // 相等, 说明找到了
                return mid;
            }
        }
        // 循环结束, 说明没找到
        return -1;
        }
}

这样三次就可以找到目标元素了。

3. 数组排序(冒泡排序)

给定一个数组, 让数组升序(降序) 排序。

算法思路

假设排升序：

1. 将数组中相邻元素从前往后依次进行比较，如果前一个元素比后一个元素大，则交换，一趟下来后最大元素就在数组的末尾

2. 依次从上上述过程，直到数组中所有的元素都排列好

上代码：

import java.util.Arrays;
public class demo {
    public static void main(String[] args) {
        int[] arr = {9, 5, 2, 6, 8, 12, 7};
        bubbleSort(arr);
        System.out.println(Arrays.toString(arr));
    }
    public static void bubbleSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length-i; j++) {
                if (arr[j-1] > arr[j]) {
                    int tmp = arr[j - 1];
                    arr[j - 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        } // end for
    } // end bubbleSort
}

当然了，冒泡排序是一种比较低效的的算法，我们Java提供了更高效的算法

public static void main(String[] args) {
        int[] arr = {9, 5, 2, 7};
        Arrays.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

4. 转轮数组

最简单的解法：使用额外的数组

我们可以使用额外的数组来将每个元素放至正确的位置。用 nn 表示数组的长度，我们遍历原数组，将原数组下标为 ii 的元素放至新数组下标为 (i+k)\bmod n(i+k)modn 的位置，最后将新数组拷贝至原数组即可。

import java.util.Arrays;
public class demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        rotate(arr,3);
        System.out.println(Arrays.toString(arr));
    }
    public static void rotate(int[] nums, int k) {
        int n = nums.length;
        int[] newArr = new int[n];
        for (int i = 0; i < n; ++i) {
            newArr[(i + k) % n] = nums[i];
        }
        System.arraycopy(newArr, 0, nums, 0, n);
    }
}

也有其他的方法：数组翻转

思路：

三步翻转法，其实轮转数组类似于之前介绍过的倒置字符串，即整体先翻转，左半部分翻转，右半部分翻转，就能得到最终结果。假设数组 nums 为 1、2、3、4、5，轮转 3 次，先整体翻转(0 ~ numsSize - 1)，数组为 5、4、3、2、1，再翻转左半部分(0 ~ k - 1)，数组为 3、4、5、2、1，最后再翻转右半部分(k ~ numsSize - 1)，数组为 3、4、5、1、2，结果出来了，这就是三步翻转法的奇妙解法

图示：

import java.util.Arrays;
public class demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        rotate(arr,3);
        System.out.println(Arrays.toString(arr));
    }
    public static void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }
    public static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;
        }
    }
}