[数据结构与算法]代码随想录算法训练营第一天

数组

数组理论基础

注意：

数组下标都是从0开始的。

数组内存空间的地址是连续的，所以我们在删除或者添加元素时，就要移动其他的元素。

数组元素不能删除在，只能覆盖。

二分查找

题目：LeetCode.704

前提条件是数组为有序数组，同时数组中没有重复元素。

写法一：我们将target定义在一个左闭右闭的区间里。

class Solution {
    public int search(int[] nums, int target) {
        int left  = 0;
        int right = nums.length - 1;
        if (target < nums[0] || target > nums[nums.length - 1]) return -1;
        while (left <= right){
            int mid = left + ((right - left) / 2);
            if (target == nums[mid]) return mid;
            else if(target < nums[mid]) right = mid - 1;
            else left = mid + 1;
        }
        return -1;

    }
}

写法二：我们将target定义在一个左闭右开的区间里。

class Solution {
    public int search(int[] nums, int target) {
        // 避免当 target 小于nums[0] nums[nums.length - 1]时多次循环运算
        if (target < nums[0] || target > nums[nums.length - 1]) {
            return -1;
        }
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + ((right - left) / 2);
            if (nums[mid] == target)
                return mid;
            else if (nums[mid] < target)
                left = mid + 1;
            else if (nums[mid] > target)
                right = mid;
        }
        return -1;
    }
}

移除元素

数组是以引用的方式传递的

数组中的元素无法真正移除，只能靠后一个元素覆盖前一个元素，返回移除后的数组没有意义

题目：LeetCode.27

写法一：暴力解法

使用两个for循环，第一个for循环遍历数组，第二个for循环更新数组。

class Solution {
    public int removeElement(int[] nums, int val) {
        int length = nums.length;
        for (int i = 0 ; i < length ; i++){
            if (nums[i] == val){
                for (int j = i + 1 ; j < length ; j++){
                    nums[j -1] = nums[j];
                }
            i--;
            length--;
            }
        }
        return length;
    }
}
// 时间复杂度：O(n^2)
// 空间复杂度：O(1)

写法2：双指针算法

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

class Solution {
    public int removeElement(int[] nums, int val) {
        int slowindex = 0;
        for(int fastindex = 0 ; fastindex < nums.length ; fastindex++){
            if (nums[fastindex] != val){
                nums[slowindex] = nums[fastindex];
                slowindex++;
            }
        }
        return slowindex;

    }
}

// 时间复杂度：O(n)
// 空间复杂度：O(1)

写法3：相向双指针法：

class Solution {
    public int removeElement(int[] nums, int val) {
        int left = 0;
        int right = nums.length - 1;
        while(right >= 0 && nums[right] == val) right--; 
        //将right移到从右数第一个值不为val的位置
        while(left <= right) {
            if(nums[left] == val) { 
                nums[left] = nums[right];
                right--;
            }
            left++;
            while(right >= 0 && nums[right] == val) right--;
        }
        return left;
    }
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)