[数据结构与算法]【数据结构】数组中的问题

常见的数组问题

• 排序：选择排序、插入排序、堆排序、快速排序、归并排序

• 二分查找法

• 数据结构：栈、队列、堆（底层实现都是数组）

• …

如何写出正确的程序

example：二分查找法

番外篇：二分查找法的思想在1946年提出的，第一个没有bug的二分查找法在1962年才出现。说明一个道理：真正的实现一个完全正确的算法是复杂的，只是思考算法的思想却是简单的。

对于有序数列，才能使用二分查找法（排序的作用）

代码实现

// 二分查找法
    public static int binarySearch(int[] arr, int target) {
        // 1、对边界问题处理
        if (arr == null || arr.length == 0) {
            return -1;
        }
        
        // 2、定义查找数组的范围边界 [left,right]
        int left = 0;
        int right = arr.length - 1;
        
        // 3、进行查找
        while (left <= right) {
            // 4、获取中间值得索引
            int middle = left + (right - left) / 2;
            if (target > arr[middle]) {
                left = middle + 1;
            } else if (target < arr[middle]) {
                right = middle - 1;
            } else {
                return middle;
            }
        }
        return -1;
    }

注意点：

1、LeetCode -283移动零

这里举一个例题：
LeetCode -283 移动零

解法一：暴力法

思路：从后向前找0，找到之后，后面的元素前移，将最后一个元素设置为0。

时间复杂度：O(n^2)

解法二：排队找空位，向前推进

思路：

1. 维护一个变量zeroNums记录0的个数
2. 当遍历到0时，zeroNums++；当遍历到非零数值时，查看此时的zeroNums，表示该顾客前面有zeroNums个空位，于是让这个顾客往前挪动zeroNums个位置，再将顾客挪动前的位置变成空位（置零）。只需要一遍遍历就可以完成。
3. 如果前面没有空位（zeroNums = 0），就不挪动

时间复杂度：O(n)

解法三：双向指针

思路：

1. 我们创建两个指针i和j，指针i用来遍历数组，指针j用来记录当前有多少非0元素。即遍历的时候每遇到一个非0元素就将其往数组左边挪，第一次遍历完后，j指针的下标就指向了最后一个非0元素下
   标+1。
2. 第二次遍历的时候，起始位置就从j开始到结束，将剩下的这段区域内的元素全部置为0。

移动一次，交换操作

优化：避免自己与自己进行交换。

2、计数排序和三路快排

这里举一个例题：
LeetCode -75颜色分类

个人解题方法，仅供参考

在没有思路的情况下，我们可以使用任意的排序算法 。

在此我们使用计数排序和三路快排来解决这个问题。

计数排序

适用元素个数非常有限的情况，在此题中我们分别统计0，1，2出现的次数。

缺点：将原数组遍历了多次。

三路快排：Quick Sort3 Ways

合并和使用快速排序法排序

快排的思想：

1. 先将数列中取出一个数作为基准数
2. 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，知道各区间只有一个数。

时间复杂度：O(nlog(n))

使用双指针

方法一没有利用数组nums1和nums2 已经被排序的性质

空间换时间，创建大小为m+n的数组，将nums1和nums2的元素比较后放入新数组中。

时间复杂度：O(m+n)

3、碰撞指针

这里举一个例题：
LeetCode -167 两数之和 II - 输入有序数组

根据题目要求：

• 数组长度必须>=2
• 仅存在唯一的答案
• 无解情况的处理
• 不可以重复使用相同的元素

解法一：暴力法，双层循环

for(int i =0;i<numbers.length-1;i++){
	for(int j=i+1;j<numbers.length;j++){
	    if(numbers[i]+numbers[j]== target){
	        return new int[]{i+1,j+1};
	    }
	}
}

解法二：碰撞指针

4、滑动窗口（双向指针的扩展）

这里举一个例题：
LeetCode -209长度最小的子数组

情况一

sum[1…3] = 6 6<7
所以：j指针向后移动
sum[1…4] = sum[1…3]+nums[4] = 10
记录>=目标值的子数组的长度 4

情况二

sum[1…3] = 6 6<7
所以：j指针向后移动
sum[1…4] = sum[1…3]+nums[4] = 10
记录>=目标值的子数组的长度 4

i指针向后挪动 i += 1
sum[2…4] = sum[1…4]-nums[1] = 7
记录>=目标值的子数组的长度 3