算法与数据结构之数组
个人说明：拿过国内某算法大赛全国三等。。。（渣渣）
概念
它用一组连续的内存空间，来存储一组具有相同类型的数据。
优点：查找速度快，可以快速随机访问
缺点：删除，插入效率低，大小固定，不支持动态扩展，要求内存空间必须连续
数组是一种线性表结构
基本操作（以下图都是盗的，有侵的话私聊我）
插入：
如果要想在任意位置插入元素，那么必须要将这个位置后的其他元素后移。
那么其最好的时间复杂度O(1) 最差的时间复杂度为O(n)
删除
同样的删除数据需要前移
注意事项：
如果插入的数据多的情况下，那么数组的容量是固定的，那么就存在扩容的操作。
同样的，如果删除数据多的情况下，也会出现缩容的操作
例：java的arraylist
首先，先看看ArrayList的初始化，源码如下：
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
//更根据初始值大小创建数组
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
//默认无规定初始值大小时，会创建一个空数组
//private static final Object[] EMPTY_ELEMENTDATA = {};
//待通过add方法时创建初始容量为10的数组
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
add(E e)方法的源码解析
public boolean add(E e) {
//检查是否需要扩容
ensureCapacityInternal(size + 1); // Increments modCount!!
//添加新元素
elementData[size++] = e;
return true;
}
//传入数组最小所需要的长度
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
//检查原先数组是否为空数组，返回数组所需最小长度
private static int calculateCapacity(Object[] elementData, int minCapacity) {
//判断数组是否为空。
//private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
//private static final int DEFAULT_CAPACITY = 10;
//数组为空时，返回DEFAULT_CAPACITY与minCapacity中大的数，减少扩容次数
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
//直接返回数组所需的最小长度size+1
return minCapacity;
}
//判断当前数组长度是否超过添加元素所需的最小长度
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
//如果所需最小长度大于当前数组长度
if (minCapacity - elementData.length > 0)
//进行扩容
grow(minCapacity);
//否则，不做任何处理
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
//新数组长度等于旧长度+1/2旧长度
int newCapacity = oldCapacity + (oldCapacity >> 1);
//计算newCapacity的大小
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
//private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
//拷贝到新数组，数组长度为newCapacity
elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
ArrayList缩容
ArrayList没有自动缩容机制。无论是remove方法还是clear方法，它们都不会改变现有数组elementData的长度。但是它们都会把相应位置的元素设置为null，以便垃圾收集器回收掉不使用的元素，节省内存。ArrayList的缩容，需要我们自己手动去调用trimToSize()方法，达到缩容的目的。
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
//判断当前容量与数组长度的大小关系
if (size < elementData.length) {
//如果size小于elementData.length，则将数组拷贝到长度为size的数组中，如果size==0，则将elementData 置为空数组，{}
elementData = (size == 0)
? EMPTY_ELEMENTDATA
: Arrays.copyOf(elementData, size);
}
}
有关数组的算法
以下算法只给思路（代码写一写就知道了）
数组算法注意事项
并没什么可注意的，哈哈哈哈
有一点就是：数组根据下标进行访问时，时间复杂度为O(1)，进行插入和删除操作时，时间复杂度为O(n)（主要就是结构可以让他这么屌）
算法一（一个未排序的整数数组，找出最长连续序列的长度。）
leetcode等级困难
时间要求O(n)
示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
思路：
java中Hashset数组是个没有重复元素的集合，那么可以将所有数据存入到set中，之后进行顺序删除，把数组进行遍历，把每个遍历的元素进行删除，删除的最大长度则为数组最大序列长度。
public int longestConsecutive(int[] nums) {
if(nums.length<=0){
return 0;
}
Set<Integer> set = new HashSet<>();
for(int n : nums){
set.add(n);
}
int maxv = 1;
for(int n : nums){
if(!set.remove(n)){
continue;
}
int vb = 1;
int va = 1;
while (set.remove(n-vb)){ vb++; }
while (set.remove(n+va)){ va++; }
maxv = Math.max(maxv,vb + va -1);
}
return maxv;
}
时间复杂度为O(n)空间复杂度为O(n) remove 的次数最多为n
算法二（奇偶数排序）
给定一个整数数组，请调整数组中数的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
要求时间复杂度为O(n)
思路：
双指针法，可以两个指针分别从前往后，进行交换。
算法三（两个有序整数数组成为一个有序数组）
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
思路：
双指针法
