Array | 秋泽雨

数组的基本知识

基本写法

int intArray[];
intArray = new int[20];

int b[] = new int[] { 1, 2, 3, 4 };
int b[] = {1, 2, 3, 4}; // latest java can use this.
for (int each: b) {
  System.out.println(each);
}

Student student[] = new Student[5];
student[1] = new Student("student1");

内存存储
数组是计算机分配的一组连续的内存空间.
数组特点:
- 数组的直接父类：Object
- 每个数组都实现了 Cloneable 和 java.io.Serializable.
- 数组的length 是属性，不是方法
- 数组是一块连续空间
算法复杂度计算:
复杂度计算

实现一个动态数组（可自动调整大小的可变数组ArrayList）
ArrayList特点:
- 基于数组实现的List类，可以动态增加或减小。
- ArrayList的用法和Vector向类似,ArrayList和Vector的区别是：ArrayList是线程不安全的，当多条线程访问同一个ArrayList集合时，程序需要手动保证该集合的同步性，而Vector则是线程安全的。
- arrayList由于本质是数组，所以它在数据的查询方面会很快，而在插入删除这些方面，性能下降很多，有移动很多数据才能达到应有的效果
- arrayList可以存放null
- arrayList实现了RandomAccess，所以在遍历它的时候推荐使用for循环
- 扩容的代价非常大，因此每次超出都会扩容2倍, remove 的时候并不会回收内存。

时间复杂度

空间复杂度

Leetcode 专业术语

原地算法：原地算法不依赖额外的资源或者依赖少数的额外资源。

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的原地算法。

  // o(k*n) = O(n)
  class Solution {
    public void rotate(int[] nums, int k) {
        int length = nums.length;
        int temp;
        for (int i = 0; i < k; i++) {
            temp = nums[0];
            nums[0] = nums[length - 1];
            for (int j = length - 2; j > 0; j--) {
                nums[j + 1] = nums[j];
            } 
            if (nums.length > 1) {
                nums[1] = temp;
            } else {
                nums[0] = temp;
            }
        }
    }
}

  class Solution {
    public void rotate(int[] nums, int k) {
        int numsLength = nums.length;
        int realK = k % numsLength;
        int[] tempNums = new int[realK];
        int pointIndex = numsLength - realK; 
        for (int i = pointIndex; i< numsLength; i++) {
            tempNums[i + realK - numsLength] = nums[i];
        }
        
        for (int i = pointIndex - 1; i>= 0;  i--) {
            nums[i + realK] = nums[i];
        }
        for (int i = 0; i < realK; i ++) {
            nums[i] = tempNums[i];
        }
    }
}

有效的山脉数组：

  class Solution {
    public boolean validMountainArray(int[] A) {
        if(A.length < 3) {
            return false;
        }
        int i, j;
        boolean isMountain = true;
        int top = 0;
        int topIndex = 0;
        
        // 采用统一流程比较去重、最大值
        for (i = 0; i < A.length; i ++) {
            if (A[i] > top) {
                top = A[i];
                topIndex = i;
            }
            if((i < A.length - 1) && (A[i] == A[i + 1])) {
                isMountain = false;
                break;
            }
        }
        if (!isMountain || topIndex == 0 || topIndex == A.length - 1) {
            return false;
        }
        
        for (i = topIndex; i > 0; i --) {
            if (A[i - 1] > A[i]) {
                isMountain = false;
                break;
            }
        }
        if (isMountain) {
            for (i = topIndex; i < A.length - 1; i ++) {
                if (A[i] < A[i + 1]) {
                    isMountain = false;
                    break;
                }
            }
        }
        return isMountain;
    }
}

  // 1. 顶点不在2端
  // 2. 定点左侧曾、右侧减
  class Solution {
    public boolean validMountainArray(int[] A) {
    // 1. 顶点不在2端
    // 2. 定点左侧曾、右侧减
        int maxValue = 0;
        int maxIndex = 0;
        int i;
        for (i = 0; i < A.length; i ++) {
            if (A[i] > maxValue) {
                maxValue = A[i];
                maxIndex = i;
            }
        }
        
        if (maxIndex == 0 || maxIndex == A.length - 1) {
            return false;
        }
        
        boolean isMountain = true;
        for (i = 0; i < maxIndex; i ++) {
            if (A[i] > A[i+1]) {
                isMountain = false;
                break;
            }
        }
        
        if (!isMountain) {
            return false;
        }
        
        for (i = maxIndex; i < A.length - 1; i ++) {
            if (A[i] <= A[i+1]) {
                isMountain = false;
                break;
            }
        }
        return isMountain;
    }
}

递增直到递减

class Solution {
    public boolean validMountainArray(int[] A) {
      if(A.length < 3) {
            return false;
        }
        //递增直到递减
        int i;
        boolean isUp = true;
        boolean isMountain = true;
        
        // 如果开始不递增，最后不递减，则不符合
        if (A[0] >= A[1] || A[A.length - 2] <= A[A.length -1]) {
            return false;
        }
    

        for(i = 1; i < A.length - 2; i++) {
            if (isUp && A[i] > A[i+1]) {
                isUp = false;
            } else if ((!isUp) && A[i] <= A[i + 1]) {
                isMountain = false;
                break;
            }
        }
        if (isMountain) {
            return true;
        } else {
            return false;
        }
    }
}

困难Letcoode题: https://leetcode-cn.com/problems/find-in-mountain-array/
给你一个山脉数组 mountainArr，请你返回能够使得 mountainArr.get(index) 等于 target 最小的下标 index 值。
如果不存在这样的下标 index，就请返回 -1。
所谓山脉数组，即数组 A 假如是一个山脉数组的话，需要满足如下条件：

首先，A.length >= 3

其次，在 0 < i < A.length - 1 条件下，存在 i 使得：
A[0] < A[1] < … A[i-1] < A[i]
A[i] > A[i+1] > … > A[A.length - 1]
你将不能直接访问该山脉数组，必须通过 MountainArray 接口来获取数据：
MountainArray.get(k) - 会返回数组中索引为k 的元素（下标从 0 开始）
MountainArray.length() - 会返回该数组的长度
注意：
对 MountainArray.get 发起超过 100 次调用的提交将被视为错误答案。此外，任何试图规避判题系统的解决方案都将会导致比赛资格被取消。
为了帮助大家更好地理解交互式问题，我们准备了一个样例 “答案”：https://leetcode-cn.com/playground/RKhe3ave，请注意这不是一个正确答案。
示例 1：
输入：array = [1,2,3,4,5,3,1], target = 3
输出：2
解释：3 在数组中出现了两次，下标分别为 2 和 5，我们返回最小的下标 2。
示例 2：
输入：array = [0,1,2,4,2,1], target = 3
输出：-1
解释：3 在数组中没有出现，返回 -1。

class Solution {
    public int findInMountainArray(int target, MountainArray mountainArr) {
        return this.findInPart(target, mountainArr, 0, mountainArr.length() - 1);
    }
    public int findInPart(int target, MountainArray mountainArr, int startIndex, int endIndex)          {
            int length = mountainArr.length();
            int midIndex = (endIndex - startIndex + 1) / 2 + startIndex;
            int midValue = mountainArr.get(midIndex);
            int lastIndex = midIndex - 1;
            int lastValue;
            int nextValue;
            int nextIndex = midIndex + 1;
            int targetIndex = -1;
            if(midIndex > startIndex + 1 && midIndex < endIndex - 1) {
                // 还能继续分，并且寻找
                lastValue = mountainArr.get(lastIndex);
                nextValue = mountainArr.get(nextIndex);
                if (midValue > lastValue && midValue > nextValue) {
                    // 山顶
                    if (midValue < target) {
                        // 不存在，不用继续找了
                        return -1;
                    } else if (midValue == target) {
                        // 找到唯一解，返回。
                        targetIndex = midIndex;
                        return targetIndex;
                    } else {
                        // 可能有2个解。
                        // 左侧求解，求得则结束
                        targetIndex = this.findInPart(target, mountainArr, startIndex, midIndex);
                        // 左侧得解
                        if (targetIndex != -1) {
                            return targetIndex;
                        } else {
                            // 左侧无解，寻求右侧
                            return this.findInPart(target, mountainArr, midIndex, endIndex);
                        }
                    }
                    
                } else if (midValue > lastValue && midValue < nextValue) {
                    // 前半
                    if (midValue == target) {
                        // 找到
                        return midIndex;
                    } else if (midValue > target) {
                        // 继续2边寻找，左右都需要
                        // 可能有2个解。
                        // 左侧求解，求得则结束
                        targetIndex = this.findInPart(target, mountainArr, startIndex, midIndex);
                        // 左侧得解
                        if (targetIndex != -1) {
                            return targetIndex;
                        } else {
                            // 左侧无解，寻求右侧
                            return this.findInPart(target, mountainArr, midIndex, endIndex);
                        }
                    } else {
                        return this.findInPart(target, mountainArr, midIndex, endIndex);
                    }
                } else {
                    // 后半边
                    // 左侧求解
                    targetIndex = this.findInPart(target, mountainArr, startIndex, midIndex);
                    if (targetIndex != -1) {
                        return targetIndex;
                    } else if (midValue == target) {
                        // 居中
                        return midIndex;
                    } else {
                        // 左侧无解，寻求右侧
                        return this.findInPart(target, mountainArr, midIndex, endIndex);
                    }
                }
            } else {
                // 分左半边拆到最细，无法再分
                if(midIndex == startIndex) {
                    if (midValue == target) {
                        return midIndex;
                    } else {
                        // 右边如果未到边界，则触发
                        if (midIndex < endIndex - 1) {
                            return this.findInPart(target, mountainArr, midIndex, endIndex);
                        } else {
                            nextValue = mountainArr.get(endIndex);
                            if (nextValue == target) {
                                return endIndex;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (midIndex == startIndex + 1){//..
                    lastValue = mountainArr.get(startIndex);
                    if (midValue == target) {
                        return midIndex;
                    } else if (lastValue == target) {
                        return startIndex;
                    } else {
                        if (midIndex < endIndex - 1) {
                            return this.findInPart(target, mountainArr, midIndex, endIndex);
                        } else {
                            nextValue = mountainArr.get(endIndex);
                            if (nextValue == target) {
                                return endIndex;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else if (midIndex == endIndex) {
                    if (midValue == target) {
                        return midIndex;
                    } else {
                        if (midIndex > startIndex + 1) {
                            return this.findInPart(target, mountainArr, startIndex, midIndex);
                        } else {
                            lastValue = mountainArr.get(startIndex);
                            if (lastValue == target) {
                                return startIndex;
                            } else {
                                return -1;
                            }
                        }
                    }
                } else {
                    nextValue = mountainArr.get(endIndex);
                    if (midValue == target) {
                        return midIndex;
                    } 
                    
                    if (midIndex > startIndex + 1) {
                        targetIndex =  this.findInPart(target, mountainArr, startIndex, midIndex);
                    } else {
                            lastValue = mountainArr.get(startIndex);
                            if (lastValue == target) {
                                return startIndex;
                            } else {
                                return -1;
                            }
                    }
                    if (targetIndex == -1) {
                        if (nextValue == target) {
                            return endIndex;
                        } else {
                            return -1;
                        }
                    }
                    return targetIndex;
                }
            }
        }
    }

数组的基本知识

实现一个动态数组（可自动调整大小的可变数组ArrayList）

时间复杂度

空间复杂度

Leetcode 专业术语