【LeetCode】一、数组相关（双指针算法 + 置换）

1、算法复杂度

1.1 时间复杂度

算法的执行时间与输入值之间的关系（看代码实际总行数的变化） ⇒ 常对幂指阶

1.2 空间复杂度

算法存储空间与输入值之间的关系（看变量的数量或者对象的数量）

2、数组

数组特点：

• 所占的内存空间连续
• 存储的元素类型相同

访问、搜索、插入、删除的时间复杂度：

访问时，时间复杂度为O(1)

a[i] = a[0]地址 + i * 元素类型所占字节

搜索时，需要遍历，直到找到a[i]的值等于所查的value，复杂度为O(n)，插入和删除时，最坏的情况在数组的开头进行增删，后面的元素都得后退或者前移一格，或者说插入引起了数组的copy到扩容后的新数组，则也是O(n)

3、leetcode485：最大连续1的个数

思路：遍历数组，出现一个1就把计数 +1，出现一个0则计数置为0，置为0之前存一下当前的计数值

public class P485 {public static void main(String[] args) {int[] array = {1, 0, 1, 1, 0, 1, 1, 1, 0, 1};System.out.println(column(array));}public static int column(int[] array) {if (null == array || array.length == 0) {return 0;}int result = 0;// 被出现的0打断计数后，存下目前的最大计数值int resultTemp = 0;for (int i : array) {if (i == 1) {result = result + 1;}if (i == 0) {resultTemp = Math.max(result, resultTemp);// 置为0，重新计数result = 0;}}return Math.max(result, resultTemp);}
}

测试：

4、leetcode283：移动0

一开始想的是：遍历找为0的元素，找到一个就将其后面的所有元素往前移动一位，然后将这个为0的元素自身扔在数组末尾。操作次数太多。

转向考虑找非0的，找到第一个，就将其放到index = 0 的位置，并且index计数加一，准备等下一个非0的元素，依次往后放非0元素，遍历完后，index后面剩下的空位都补0即可。

public class P283 {public static void main(String[] args) {int[] array = {1, 0, 9, 0, 6, 8, 0};for (int i : move(array)) {System.out.print(i + ",");}}public static int[] move(int[] array) {// 记录非0元素下标位置（像一个指针，告诉我目前非0元素放到几号空位了）int index = 0;for (int i = 0; i < array.length; i++) {if (array[i] != 0) {// 非0元素前移array[index] = array[i];index++;}}// 剩余空位全部为0for (; index < array.length ; index++) {array[index] = 0;}return array;}
}

5、leetcode27：移除元素

思路：双指针算法 + 置换

左右两个指针，L指针向右找等于要移除的val的位置停下来，R指针向左找不等于val的位置停下来，然后两个位置的元素置换。如此，右边的就全是要移除的值，左边的数量即为该题的返回值。

当左指针L >= 右指针R时，说明已经全部遍历了一遍了，此时，看下，如果L所在的值为val，说明其前面全都是不等于val的值，比如L为4，说明当前位置下标为4，前面为0、1、2、3这四个元素，返回的数量就是4，也即L的值，反之，L所在的值不等于val，说明当前位置的值及其前面的值，都是不等于val的值，数量 = 索引 + 1，返回L + 1

public class P27 {public static void main(String[] args) {int[] array = {1, 0, 9, 0, 6};System.out.println(remove(array, 0));}public static int remove(int[] array, int val) {if (array == null || array.length == 0) {return 0;}int left = 0;int right = array.length - 1;while (left < right) {// 没找到左边等于val的值前，一直找while (left < right && array[left] != val) {left++;}// 没找到右边不等于val的值前，一直找while (left < right && array[right] == val) {right--;}// 置换，把数组中等于value的元素扔右边int temp = array[left];array[left] = array[right];array[right] = temp;}if (array[left] == val) {return left;} else {return left + 1;}}
}

测试：