数组
1. 概念：
数组是在内存中存储相同数据类型的连续的空间
声明一个数组就是在内存空间中划出一串连续的空间
数组名 代表的是连续空间的首地址
通过首地址可以依次访问数组所有元素
元素在数组中的排序叫做下标 从零开始
2. 区分元素和索引（下标）
举例：
数组 [1,22,3,44,5]
数组的元素是数组内部具体的值，1,22,3,44,5
下标（索引）从零开始， 0,1,2,3,4,
3. 访问(Access)和搜索(Search)
**访问 **是 通过下标是找这个元素的值
**搜索 **是 直接查找元素
4. 数组的四种方法
1. 访问(Access)：O(1)
可以通过数学公式找到
举例：
int a[1,2,3]访问每个元素，假如数组内存地址是10，
a[1]的地址为10+1*4=14，其中4为int占用4个字节
2. 搜索(Search)：O(N)
从头到尾遍历
最差为遍历到最后找到想找的元素
3. 插入(Insert)： O(N)
将 要插入的元素 的 后面的元素 都往后移
最差的情况是在第一个元素后面插入，那么之后的元素都往后移
如果插入时后移空间不够，则需要开辟新的内存空间来执行操作
4. 删除(Delete)：O(N)
删除一个元素时，其余元素前移，因为数组的空间是连续的
最差情况是，前面删除一个元素，后面的都往前移
对比两个数组也就是对比以上内容
5. 特点：
读 √
写 ×
6. 常用操作
1. 创建数组
四种常用方法：
int[] arr = {1,2,3};int[] arr = new int[]{1,2,3};
常用：
int[] arr = new int[3];当不知道数组应该放多少个元素，用这个ArrayList<Integer> arr =new ArrayList<>();不需要指定长度和元素，用这个
2. 添加元素
使用的是ArrayList的方式
O(1)是插在尾端，O(N)是插在中间
3. 访问元素
c[1]是普通方法，
arr.get(1)是ArrayList的方法
4. 修改（更新）元素
c[1]是普通方法，
arr.set(1,11)是ArrayList的方法
5. 删除元素
使用的是ArrayList的方式
6. 数组的长度
这两个方法时间复杂度是O(1),每次操作，内部有个count会帮助计算
c.length是普通方法，
arr.size()是ArrayList的方法
7. 遍历元素
这两个方法时间复杂度是O(N)
c.length是普通方法，
arr.size()是ArrayList的方法
8. 查找元素
普通方式，一个个遍历，然后看有没有要找的那个元素
ArrayList方式，用
contains()方法
9. 数组排序(内置排序法)
用的是自带的排序方法，并非自己写的
普通和ArrayList都有
sort()方法从大到小排序：
普通：
Arrays.sort(T[],Collections.reverseOrde());此题中，T[]是Integer[] c,要传对象方式 ArrayList:
Collections.sort(arr, Collections.reverseOrder( ));
Leetcode
485.最大连续1的个数
1.先判断数组长度是否为0或者数组为空
2.定义一个计数器count，和存放结果的result
3.遍历数组，如果元素为1，计数器+1
如果不为1，result=result和count的最大值，同时计数器置为0
4.遍历完毕后，返回=result和count的最大值
代码如下：
public class array {
public int findMaxConsecutiveOnes(int[] nums) {
if (nums.length == 0 || nums == null) {
return 0;
}
int count = 0;
int result = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 1) {
count++;
} else {
result = Math.max(result, count);
count = 0;
}
}
return Math.max(result, count);
}
}
283.移动零
方法一：
两次遍历
我们创建两个指针i和index，第一次遍历的时候指针index用来记录当前有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪，第一次遍历完后，j指针的下标就指向了最后一个非0元素下标。
第二次遍历的时候，起始位置就从index开始到结束，将剩下的这段区域内的元素全部置为0。
public class zero {
public void moveZeroes(int[] nums) {
int index = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[index] = nums[i];
index++;
}
}
for (int i = index; i < nums.length; i++) {
nums[i] = 0;
}
}
动画演示 283.移动零 - 移动零 - 力扣（LeetCode） (leetcode-cn.com)
方法二：
参考了快速排序的思想，快速排序首先要确定一个待分割的元素做中间点x，然后把所有小于等于x的元素放到x的左边，大于x的元素放到其右边。
这里我们可以用0当做这个中间点，把不等于0(注意题目没说不能有负数)的放到中间点的左边，等于0的放到其右边。
这的中间点就是0本身，所以实现起来比快速排序简单很多，我们使用两个指针i和j，只要nums[i]!=0，我们就交换nums[i]和nums[j]
package qi.array;
/**
* 移动0
*/
public class zero {
public void moveZeroes(int[] nums) {
if(nums==null) {
return;
}
//两个指针i和j
int j = 0;
for(int i=0;i<nums.length;i++) {
//当前元素!=0，就把其交换到左边，等于0的交换到右边
if(nums[i]!=0) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j++] = tmp;
}
}
}
27.移除元素
方法一：
左右指针
判断
定义两个指针
在 左< 右 的时候
如果左 != 值，左指针右移，
如果 右 = 值，右指针左移
交换左右指针上的的元素
返回，如果 左指针或者右指针（因为最后两个指针会指向同一个位置） 上的元素等于val，返回当前指针，否则返回指针加一
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) {
return 0;
}
int l = 0;
int r = nums.length - 1;
while (l < r) {
while (l < r && nums[l] != val) {
l++;
}
while (l < r && nums[r] == val) {
r--;
}
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
return nums[l] == val ? l : l + 1;
}
方法二：
快慢指针
把不为val的放在j的位置上
最后返回j的下标
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) {
return 0;
}
int j = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[j] = nums[i];
j++;
}
}
return j;
}
方法三：
暴力破解法
将要移除的元素的后面的所有元素往前移
public int removeElement(int[] nums, int val) {
int size = nums.length;
for (int i = 0; i < size; i++) {
if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位
for (int j = i + 1; j < size; j++) {
nums[j - 1] = nums[j];
}
i--; // 因为下表i以后的数值都向前移动了一位，所以i也向前移动一位
size--; // 此时数组的大小-1
}
}
return size;
}
