算法与数据结构(二)-数组

算法与数据结构(二) - 数组

定义

数组(Array)是有序的元素序列。 [1] 若将有限个类型相同的变量的集合命名,那么这个名称为数组名。组成数组的各个变量称为数组的分量,也称为数组的元素,有时也称为下标变量。用于区分数组的各个元素的数字编号称为下标。数组是在程序设计中,为了处理方便, 把具有相同类型的若干元素按有序的形式组织起来的一种形式。 [1] 这些有序排列的同类数据元素的集合称为数组。

数组常见问题算法

二分查找

二分查询法就是讲数据进行两份化处理. 左边区域left 右边区域right.再取中间值,进行比较,判断要求数据在哪个区域

大家写二分法经常写乱,主要是因为对区间的定义没有想清楚,区间的定义就是不变量。要在二分查找的过程中,保持不变量,就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作,这就是循环不变量规则。

写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。

例题:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

示例 1:

输入: nums = [-1,0,3,5,9,12], target = 9     
输出: 4       
解释: 9 出现在 nums 中并且下标为 4     

示例 2:

输入: nums = [-1,0,3,5,9,12], target = 2     
输出: -1        
解释: 2 不存在 nums 中因此返回 -1      

提示:

  • 你可以假设 nums 中的所有元素是不重复的。
  • n 将在 [1, 10000]之间。
  • nums 的每个元素都将在 [-9999, 9999]之间。

假设存在数组:1,2,3,4,7,9,10中查找元素2.

public static int twolinkSearch(int[] nums, int target) {
    //当 target 小于nums[0] 或者nums[nums.length - 1]时返回-1
    if (target < nums[0] || target > nums[nums.length - 1]) &#123;
        return -1;
    &#125;
    int left = 0;
    int right = nums.length - 1;
    while (left <= right) &#123;
        int mid = left + ((right - left) / 2); // 防止溢出 等同于(left + right)/2
        if (nums[mid] ==target)
            return mid;
        else if (nums[mid] < target) // 中间数小于目标值,则目标值在右半区
            left=mid+1;
        else if (nums[mid]>target) // 中间数大于目标值,则目标值在左半区
            return right=mid-1;
    &#125;
    return -1;
&#125;

移除元素

要知道数组的元素在内存地址中是连续的,不能单独删除数组中的某个元素,只能覆盖。

例题:给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。

提示:不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并原地修改输入数组。

示例 1:

给定 nums = [3,2,2,3], val = 3, 函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。 你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,1,2,2,3,0,4,2], val = 2, 函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。

暴力循环解法

使用两层for循环,一个for循环遍历数组元素 ,第二个for循环更新数组。

// 时间复杂度:O(n^2)
// 空间复杂度:O(1)
public static int foreachDeleteVar(int[] nums,int target)&#123;
    int length = nums.length;
    for (int i=0;i<length;i++)&#123;
        if (nums[i]==target)&#123; // 发现需要移除的元素,就将后面数组集体向前移动一位,进行覆盖操作
            for (int j=i+1;j<length;j++)&#123;
                nums[j-1]=nums[j];
            &#125;
            i--;  // 因为下表i以后的数值都向前移动了一位,所以i也向前移动一位
            length--;  // 此时数组的大小-1
        &#125;
    &#125;
    return length;
&#125;

双指针法

双指针法(快慢指针法): 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

双指针法(快慢指针法)在数组和链表的操作中是非常常见的,很多考察数组、链表、字符串等操作的面试题,都使用双指针法。

// 时间复杂度:O(n)
// 空间复杂度:O(1)
public static int fastSlowIndexDeleteVar(int[] nums, int target) &#123;
    int fast = 0;
    int slow;
    for (slow = 0; fast < nums.length; fast++) &#123;
        if (nums[fast] != target) &#123;
            nums[slow] = nums[fast];
            slow++;
        &#125;
    &#125;
    return slow;
&#125;

滑动窗口法

所谓滑动窗口,就是不断的调节子序列的起始位置和终止位置,从而得出我们要想的结果。通常使用在求和的数组上.

滑动窗口也可以理解为双指针法的一种!只不过这种解法更像是一个窗口的移动,所以叫做滑动窗口更适合一些。

例题:给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。

示例:

输入:s = 7, nums = [2,3,1,2,4,3] 输出:2 解释:子数组 [4,3] 是该条件下的长度最小的子数组。

使用滑动窗口法:

本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。

窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,窗口的起始位置设置为数组的起始位置就可以了。

public static int miniSubLen(int[] nums, int target) &#123;
    int start = 0;
    int sum = 0;
    int result = Integer.MAX_VALUE;
    for (int end = 0;end < nums.length;end++)&#123;
        sum += nums[end];
        while (sum >= target)&#123;  //判断结果是否大于或等于目标值
            result = Math.min(result,end - start + 1);  //判断结果的数组长度,如果更小则替代原结果
            sum -= nums[start++];  //减掉开始指针的值,并将开始指针向前移动
        &#125;
    &#125;
    return result == Integer.MAX_VALUE ? 0 : result;
&#125;

数列排序

进行数列排序算法:

插入排序

每次将一个数字插入一个有序的数组里,成为一个长度更长的有序数组,有限次操作以后,数组整体有序。

/**
* 时间复杂度:O(N^2)
* 空间复杂度:O(1)
*/
public int[] sortArray(int[] nums) &#123;
        int len = nums.length;
        // 循环不变量:将 nums[i] 插入到区间 [0, i) 使之成为有序数组
        for (int i = 1; i < len; i++) &#123;
            int temp = nums[i]; // 提前将其当前指针的值存储
            int j = i;  //用作遍历当前指针前的元素的指针
            //判断前一个数是否大于当前数, 注意边界 j > 0 
            while (j > 0 && nums[j - 1] > temp) &#123;
                nums[j] = nums[j - 1];
                j--;
            &#125;
            nums[j] = temp;
        &#125;
        return nums;
&#125;

在小区间内执行排序任务的时候,可以转向使用「插入排序」

归并排序

归并这个词语的含义就是合并,并入的意思.

归并排序使用的就是分治思想。顾名思义就是分而治之,将一个大问题分解成若干个小的子问题来解决。

将原数组分区域,分别排序,借助额外空间,合并分区域的有序数组,得到更长的有序数组.

而其中的归并主要实现思想为:

通过双指针从左自右比较两个指针指向的值,将较小的一方存入大集合中,存入之后较小一方的指针向前移动,并继续比较,直到某一小集合的元素全部都存到大集合中。

当某一小集合元素全部放入大集合中(指针到尾部无法继续后),则需将另一小集合中剩余的所有元素存到大集合中.

    public static void sortIntArray(int[] target) &#123;
        mergeSort(target, 0, target.length - 1);
    &#125;

    /**
     * 对数组 nums 的子区间 [left, right] 进行归并排序
     *
     */
    private static void mergeSort(int[] nums, int left, int right) &#123;
        if (left < right) &#123;
            int mid = left + (right - left) / 2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid + 1, right);
            //合并小区域数组排序
            mergeOfTwoSortedArray(nums, left, mid, right);
        &#125;
    &#125;

    /**
     * 合并两个有序数组:先把值复制到临时数组,再合并回去
     *
     */
    private static void mergeOfTwoSortedArray(int[] arr, int left, int mid, int right) &#123;
        /** 第一步,定义一个新的临时数组 **/
        int[] tempArr = new int[right - left + 1];
        // 两个数列的指针
        int temp1 = left, temp2 = mid + 1;
        int index = 0;
        /** 第二步,比较每个指针指向的值,小的存入大集合 **/
        while (temp1 <= mid && temp2 <= right) &#123;
            if (arr[temp1] <= arr[temp2]) &#123;
                tempArr[index] = arr[temp1];
                index++;
                temp1++;
            &#125; else &#123;
                tempArr[index] = arr[temp2];
                index++;
                temp2++;
            &#125;
        &#125;
        /** 第三步,将未全部存入的小集合剩余元素存到大集合中 **/
        if (temp1 <= mid) &#123;
            System.arraycopy(arr, temp1, tempArr, index, mid - temp1 + 1);
        &#125;
        if (temp2 <= right) &#123;
            System.arraycopy(arr, temp2, tempArr, index, right - temp2 + 1);
        &#125;
        System.arraycopy(tempArr,0,arr,0+left,right-left+1);
    &#125;

while 中两个指针循环,可以在内部进行判断,当其指针到边缘位置时break退出,避免不必要的循环步骤,性能又能提升40%。

while (nums[less]<pivot)&#123;
    if (less==right)&#123;
        break;
    &#125;
    less++;
&#125;
while (nums[greater]>pivot)&#123;
    if (greater==left)&#123;
        break;
    &#125;
    greater--;
&#125;
算法名称 最好时间复杂度 最坏时间复杂度 平均时间复杂度 空间复杂度 是否稳定
归并排序 O(nlogn) O(nlogn) O(nlogn) O(n) 稳定

快速排序

快速排序也是一种分治的排序算法.它将数组通过切分(partition)分成两个子数组,将两部分独立地排序.快速排序和归并排序是互补的.

快速排序基本思想:

1.先从数组中找一个基准数

2.让其他比它大的元素移动到数列一边,比他小的元素移动到数列另一边,从而把数组拆解成两个部分。

3.再对左右区间重复第二步,直到各区间只有一个数。

在快速排序中,首先随机打乱数组排序.然后取出切分元素,它把数组大于小于它的进行划分.

然后分别将左右部分循环进行快速排序,

一边循环到只有大小一为止,排序到最后直接合并即可(不需要像归并排序最后还需要合并排序).

  • 版本 1:基本版本:把等于切分元素的所有元素分到了数组的同一侧,但可能会造成递归树倾斜;
/**
 * 快速排列
 * @param nums
 * @param left
 * @param right
 */
public void quickSort(int[] nums, int left, int right) &#123;
    // 判断是否 长度是否为0 ,为0则为排序完毕的元素
    if (right - left + 1 <= 0)&#123;
        return;
    &#125;
    //获取切点元素位置
    int pIndex = partition(nums, left, right);
    quickSort(nums, left, pIndex - 1);  //左侧
    quickSort(nums, pIndex + 1, right);  //右侧
&#125;

/**
 * 切分数组
 *
 * @param nums
 * @param left
 * @param right
 */
private int partition(int[] nums, int left, int right) &#123;
    //获取随机下标数(切分元素)
    int randomIndex = new Random().nextInt(right - left + 1) + left;
    swap(nums, left, randomIndex);  //将头部与切分元素进行交换

    // 切分元素值
    int pivot = nums[left];
    // 切分元素下标位置
    int less = left;
    for (int i = left + 1; i <= right; i++) &#123;
        if (nums[i] < pivot) &#123; //指针的值小于切分值
            less++;
            swap(nums, i, less); //切分值与其互换位置
        &#125;
    &#125;
    swap(nums, left, less);
    return less;
&#125;

/**
 * 交换两个值位置
 */
private void swap(int[] nums, int index1, int index2) &#123;
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
&#125;

版本2:双指针法 - 把等于切分元素的所有元素等概率地分到了数组的两侧,避免了递归树倾斜,递归树相对平衡;

    /**
     * 快速排列
     *
     * @param nums
     * @param left
     * @param right
     */
    public void quickSort(int[] nums, int left, int right) &#123;
        if (left < right) &#123;
            int pIndex  =partition(nums,left,right);
            quickSort(nums,left,pIndex-1);
            quickSort(nums,pIndex+1,right);
        &#125;
    &#125;

    public int partition(int[] nums, int left, int right) &#123;
        int randomIndex = left + new Random().nextInt(right - left + 1);
        swap(nums, randomIndex, left);

        int pivot = nums[left];
        // 两个指针:一个从前到后,一个从后向前
        int less = left + 1;
        int greater = right;
        while (true)&#123;
            while (less<=right&&nums[less]<pivot)&#123;
                less++;
            &#125;
            while (greater>left&& nums[greater]>pivot)&#123;
                greater--;
            &#125;
            // 当小指针大于或等于大指针退出循环
            if (less>=greater)&#123;
                break;
            &#125;
            // 当less指针大于等于 且greater指针小于等于时,同时双指针移动
            swap(nums,less,greater);
            less++;
            greater--;
        &#125;
        swap(nums,left,greater);
        return greater;
    &#125;

    public void swap(int[] nums, int index1, int index2) &#123;
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    &#125;