Java-数据结构-数组

一. 数组简单介绍

        数组是在程序设计中，把具有相同类型的若干元素按有序的形式组织起来的一种形式。 数组 （Array）是有序的元素序列。若将有限个类型相同的变量的集合命名，那么这个名称为数组名。组成数组的各个变量称为数组的分量，也称为数组的元素。

      数组作为线性表的实现方式之一，数组中的元素在内存中是连续存储的，且每个元素占相同大小的内存。

一维数组

         数组是存储在连续内存空间上的相同类型类型的集合，其通过索引（脚标）快速访问每个元素的值。在大多数编程语言中，脚标（索引）从 0 算起。数组是由相同类型的数据元素构成的有限集合，一维数组可以看作一个线性表。一维数组的元素有1个下标。

        数组下标都是从0开始的。
        数组在内存空间的地址是连续的。
        删除或者增添元素时难免要移动其他元素的地址。//把元素放在其它位置上

二维数组 

        二维数组也可以看作一个线性表X=(X0，X1，X2，…，Xn-1)，只不过每一个数据元素Xi也是一个线性表。二维数组的元素中有 2 个下标。

        但无论是一维还是二维，数组是在内存中连续存储多个元素的结构，在内存中的分配也是连续的，数组中的元素通过数组下标进行访问，数组下标从0开始。 

二. 数组的优缺点

优点

1. 按照索引查询元素速度快
2. 按照索引遍历数组方便

缺点

1. 数组的大小固定后就无法扩容了
2. 数组只能存储一种类型的数据
3. 添加，删除的操作慢，因为要移动其他的元素。
数组适用频繁查询，对存储空间要求不大，很少增加和删除的情况。

三. leetcode实战

1. leetcode66 加一

给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

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

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。

class Solution {
    public int[] plusOne(int[] digits) {
        for(int i = digits.length-1; i >= 0; i--){
            digits[i] = digits[i]+1;
            if(digits[i] == 10){
                digits[i] = 0;
                continue;
            }
            return digits;
        }
        if(digits[0] == 0){
            int[] new_digits = new int[digits.length+1];
            new_digits[0] = 1;
            for(int i = 1; i <= digits.length; i++){
                new_digits[i] = digits[i-1];
            }
            return new_digits;
        }
        return digits;
    }
}

 2. leetcode485. 最大连续 1 的个数

给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
输入：nums = [1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.
 

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int temp = 0;
        int res = 0;
        for(int i = 0; i < nums.length; i++){
            if(nums[i] == 1){
                temp++;
                continue;
            }
            res = Math.max(res,temp);
            temp = 0;
        }
        res = Math.max(res,temp);
        return res;
    }
}

class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        int left = 0;
        int res = 0;
        int temp = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] == 1){
                right++;
                continue;
            }
            temp = right-left;
            res = Math.max(res,temp);
            while(right < nums.length && nums[right] != 1){
                right++;
            }
            left = right;
        }
        temp = right-left;
            res = Math.max(res,temp);
        return res;
    }
}

 3. leetcode1. 两数之和 梦开始的地方

        给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap<>();
        int[] ans = new int[2];
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                ans[0] = map.get(target - nums[i]);
                ans[1] = i;
                return ans;
            }
            map.put(nums[i], i);
        }
        return ans;
    }
}

4.  leetcode 27. 移除元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = 0;
        while(right < nums.length){
            if(nums[right] == val){
                right++;
                continue;
            }
            nums[left++] = nums[right++]; 
        }
        return left;
    }
}

5.  leetcode 88. 合并两个有序数组

        给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

        请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

        注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

 输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

栈方法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int nums1_index = 0;
        int nums2_index = 0;
        int len1 = nums1.length;
        int len2 = nums2.length;
        Deque stack = new ArrayDeque<>();
        for(int i = m-1; i >= 0; i --){
            stack.push(nums1[i]);
        }
        while(!stack.isEmpty() && nums2_index < len2 ){
            if(stack.peek() <= nums2[nums2_index]){
                nums1[nums1_index++] = stack.pop();
            }
            else{
                nums1[nums1_index] = nums2[nums2_index];
                nums1_index++;
                nums2_index++;
            }
        }
        while(nums2_index < len2){
            nums1[nums1_index++] = nums2[nums2_index++];
        }
        while(!stack.isEmpty()){
            nums1[nums1_index++] = stack.pop();
        }
    }
}

倒序

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int right = n-1;
        int left = m-1;
        int cur = nums1.length-1;
        while(right >= 0 && left >= 0){
            if(nums1[left] > nums2[right]){
                nums1[cur--] =  nums1[left--];
            }
            else{
                nums1[cur--] =  nums2[right--];
            }
        }
        while(right >= 0){
            nums1[cur--] =  nums2[right--];
        }
        while(left >= 0){
            nums1[cur--] =  nums1[left--];
        }
    }
}

参考来源：

【1】CSND 千瞱 C/C++二维数组总结