数组 Array

一、数组的定义

数组是基础的线性表数据结构，当我们声明一个数组时，计算机在内存中开辟了一段连续的内存用于存储相同类型的数据。

定义中「连续内存空间」和「相同类型的数据结构」这两个特点，使数组拥有随机访问这一特性。
但同时也让数组的很多操作变得低效，例如在数组中插入或删除一个数据，为了维持其连续性的特点，则需要做数据搬移的工作。

二、数组的操作

（1）数组的基本操作

插入 Insert：在数组中插入一个新元素。
删除 Delete：在数组中删除一个已有的元素。
读取（随机访问） Read：读取数组中某个下标的值。
查找 Find：查找数组中值为目标值的元素，并返回其下标。

（2）寻址操作

数组支持以索引访问元素以及对数据进行插入和删除的操作。以索引来访问元素，是其他操作的基础，系统会给每个内存单元分配一个地址，再通过地址来访问内存中的元素。当需要随机访问数组中的某个元素时，会通过寻址公式计算出元素存储的内存地址，由此实现对该元素的访问。

a[i]_address = base_address + i * data_type_size //寻址公式

其中 data_type_size 表示每个元素的大小，例如数组中存储的是整形元素，那么这个值就是 4 字节。

（3）操作的时间复杂度

插入：O(N)，如果是添加到末尾，那只需要 O(1) 的步数，但是如果添加到数组间，异或数组起始位置，那么还涉及到后面元素的移动，因此极限情况下需要的步数是 N+1。
删除：O(N)，删除一个元素也会涉及到元素的移动，因此极限情况下需要的步数是 N+1。
读取：O(1)，计算机知道数组第一个元素的内存地址，以及数组的个数，因此只需要一步就可以得到某个下标的元素。
查找：O(N)，计算机需要先访问到下标后，才能得到对应元素，当查找的元素在最后一个位置时，查找需要的步数是 N +1。

（4）数组操作的优化

优化一：删除操作的优化与 JVM 垃圾回收算法

如同前面介绍的，数组的删除操作会涉及元素的搬运，这也是最耗费时间的操作。
如果当我们需要删除多个元素时，为了避免没被删除的元素搬运多次，我们可以考虑将记录下已经删除的数据。每次的删除操作并不是真正地搬运数据，只是记录数据已经被删除。当数组没有更多的空间存储数据时，我们再触发一次真正的删除操作没这样就大大减少了数据的搬运。
同时这也是 JVM 垃圾回收算法中的核心思想。

优化二：插入操作的优化

如果数组中的元素并非有序，只是作为一个存储数据的集合，那么可以利用一个处理技巧来避免大规模的搬移数据。
例如要在位置 K 插入一个新元素，那么可以讲 K 位置的元素搬移到数组的最后，把新数据直接放到原来 K 的位置。

优化三：对有序数组的优化

当数组这个基本数据结构升级到有序的情况之后，数组的一个操作会有一些变化。读取，添加，删除的操作和普通数组无异，然而查找的操作有了很大的提升，这里我们可以引出二分查找这个算法。
二分查找算法利用有序数组的特性，可以有效降低查找这个操作的时间复杂度：O(N) -> O(logN)。
需对二分查找算法的基本代码非常熟悉

三、常见的数组问题

（1）数组越界问题

但并非所有的语言都像 C 一样，把数组越界检查的工作丢给程序员来做，像 Java 本身就会做越界检查，比如下面这几行 Java 代码，就会抛出 java.lang.ArrayIndexOutOfBoundsException。

int[] a = new int[3]; 
a[3] = 10; // 越界操作

（2）容器的使用

ArrayList 的使用

ArrayList 可以将很多数组操作的细节封装起来，例如前面介绍的数组插入、删除数据时，需要搬移其他元素。
ArrayList 支持动态扩容，实现了每次自动扩容 1.5 倍的底层逻辑。
虽然支持动态扩容，但操作仍然是耗时的，所以如果能事先确定需要存储的数据大小，可以在创建 ArrayList 时事先指定好数据大小。

List<String> list = new ArrayList<>(10); // initial capacity

Array 和 ArrayList 的选择对比

数组本身在定义的时候需要预先指定大小，并且由于需要分配连续内存的原因，当起初我们申请了大小为10 的数组，当第 11 个元素需要存储到数组时，我们就需要重新分配一块更大的空间，将原来的数据复制过去，再将新数据插入。
ArrayList 无法存储基本类型，比如 int、long，需要封装为 Integer、Long 类，而 Autoboxing、Unboxing 都会有性能开销，如果是特别底层的开发，例如网络框架，这时候使用数组就有性能优势。
多维数组：选择数组会比容器更加直观。Object[][] array 会比ArrayList<ArrayList<Object> array更加直观。
事先知道数据大小并且对数据的操作特别简单时，数组会更加合适。
实际业务开发，首选 ArrayList，方便使用易维护。

四、相关应用及算法题

（1）二分查找

题目描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

链接：

Q704 二分查找

解题思路

利用有序数组的特性和双指针，实现每一轮操作都将目标数组的元素数量减半。

代码实现

class Solution {
		public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0;
        int r = n - 1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] < target) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return -1;
    }
}

（2）合并有序数组

题目描述

实现两个有序数组合并为一个有序数组

Q88 合并有序数组

解题思路

由于题目要求合并两个数组的元素到第一个数组中，可以从后往前处理，来避免额外的保存。注意边界条件的处理。

代码实现

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int index = m + n - 1;
        int i = m - 1;
        int j = n - 1;

        while (i >= 0 || j >= 0) {
            if (i < 0) {
                nums1[index--] = nums2[j--];
            } else if (j < 0) {
                nums1[index--] = nums1[i--];
            } else if (nums1[i] <= nums2[j]) {
                nums1[index--] = nums2[j--];
            } else {
                nums1[index--] = nums1[i--];
            }
        }
    }
}

（3）移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

Q283 移动零

解题思路

先通过一次循环把非 0 元素放到数组前面，后面再将数组空余的位置补充数字 0 即可。

从这题我们可以得到一种解题方向，就是可以从题目示意的相反角度来考虑问题。

代码实现

class Solution {
    public void moveZeroes(int[] nums) {

        int index = 0;
        for (int num : nums) {
            if (num != 0) {
                nums[index++] = num;
            }
        }
        while (index < nums.length) {
            nums[index++] = 0;
        }

    }
}

（4）只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？

Q136 只出现一次的数字

解题思路

运算符中的亦或运算，具有一下特性

0 ^ 任意数字= 数字本身。
两个数字相等时的亦或操作，结果为0；两个值不相等时，结果为 1。
亦或操作满足交换定律。

代码实现

class Solution {
    public int singleNumber(int[] nums) {
        
        int result =0;
        for (int num : nums) {
            result ^= num;
        }
        return result;
    }
}

（5）多数元素

题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

Q169 多数元素

解题思路

代码实现

class Solution {
    public int majorityElement(int[] nums) {

        int major = nums[0];
        int cnt = 1;
        
        for (int i = 1; i < nums.length; i++) {
            if (cnt == 0) {
                major = nums[i];
            }
            if (nums[i] == major) {
                cnt++;
            } else {
                cnt--;
            } 
        }
        
        return major;
    }
}

（6）删除排序数组的重复项

题目描述

给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持一致。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

Q26 Remove Duplicates from Sorted Array

解题思路

双指针，我们并不真正的去删除某个元素，而是用下标 i 来统计不同数字的个数。

代码实现

class Solution {
    public int removeDuplicates(int[] nums) {

        int i = 1;
        for (int j = 1; j < nums.length ; j++) {
            if (nums[j] != nums[j - 1]) {
                nums[i++] = nums[j];
            }
        }
        return i  ;
    }
}

（7）加一

题目描述

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。最高位数字存放在数组的首位，数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

Q66 Plus One

解题思路

我们从后往前遍历，在循环中判断是直接加一还是处理进位的情况。如果在循环中没有返回结果，则说明是 99，999 等这类特殊数字，则单独处理。

代码实现

class Solution {
    public int[] plusOne(int[] digits) {

        int n = digits.length;
        for (int i = n - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i] = digits[i] + 1;
                return digits;
            }
            digits[i] = 0;
        }
        
        digits = new int[n + 1];
        digits[0] = 1;
        return digits;
    }
}

（8）三数之和

题目描述

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。（注意：答案中不可以包含重复的三元组）

Q15 3 Sum

解题思路

代码稍显复杂，实际逻辑很简单，先对数组做一次排序，然后用二分查找的思路做比较即可。

代码实现

    /**
     * Time: O(N^2): 排序是 N*logN，循环内是 N^2，结合起来取最大值，结果即 O(N^2)
     * Space: O(1)
     */
    public static List<List<Integer>> threeSumWithSorted(int[] nums) {

        if (nums == null || nums.length == 0) {
            return new ArrayList<>();
        }

        //Time: O(N*logN)
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        int index = 0;

        // Time: O(N^2)
        while (index < nums.length - 2) {
            // 如果第一个数就 > 0， 那后面的数都大于 0 了，直接 break。
            if (nums[index] > 0) {
                break;
            }
            // 不能包含重复的三元组，所以如果当前 index 的和上一个 index 值相同时，跳过当前循环
            if (index >= 1 && nums[index] == nums[index - 1]) {
                index++;
                continue;
            }

            int dif = -nums[index];
            int l = index + 1;
            int r = nums.length - 1;

            while (l < r) {
                int sum = nums[l] + nums[r];
                if (sum == dif) {
                    result.add(Arrays.asList(nums[index], nums[l], nums[r]));
                    l++;
                    r--;
                    // 下面两个循环，同样是为了处理「不能包含重复三元素」的问题
                    while (l < r && nums[l] == nums[l - 1]) {
                        l++;
                    }
                    while (l < r && nums[r] == nums[r + 1]) {
                        r--;
                    }
                } else if (sum < dif) {
                    l++;
                } else {
                    r--;
                }
            }
            index++;
        }

        return result;
    }

（9）数组中第 K 大的元素

题目描述

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

Q215 Kth Largest Element in An Array

解题思路

可以使用小根堆来解决。

代码实现

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int num : nums) {
            pq.offer(num);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        
        return pq.peek();
    }
}

my wiki