1.数组理论基础
数组是非常基础的数据结构，在面试中，考察数组的题目一般在思维上都不难，主要是考察对代码的掌控能力
首先要知道数组在内存中的存储方式，这样才能真正理解数组相关的面试题
数组是存放在连续内存空间上的相同类型数据的集合。
数组可以方便的通过下标索引的方式获取到下标下对应的数据。
数组中有两点需要注意：
数组下标是从0开始的
数组内存空间地址是连续的
因为数组的内存空间是连续的，所以我们在删除或者增添元素的时候，就难免要移动其他元素的地址
如下所示
数组的元素是不能删的，只能覆盖
Ok，来个二维数组
Java中的二维数组可能是这样排列的
同一行是连续的，不同行的地址是不连续的
2.二分查找
给定一个 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]之间。
思路
这道题目的前提是数组为有序数组，同时题目还强调数组中无重复元素，因为一旦有重复元素，使用二分查找法返回的元素下标可能不是唯一的，这些都是使用二分法的前提条件
二分查找涉及的很多的边界条件，逻辑比较简单，就是要注意对区间的定义要清楚写二分法，区间的定义一般为两种，左闭右闭即[left, right]，或者左闭右开即[left, right)。
package com.caq.array; import org.junit.Test; import java.lang.annotation.Target; import java.util.concurrent.RecursiveTask; /** * @Date 2021/12/16 23:36 * @Version 1.0 */ public class Binaryforarrays { public static void main(String[] args) { int[] nums = {1,2,3,4,7,9,12,45}; int i = Binaryforarrays.search1(nums, 12); System.out.println(i); } public static int search1(int[] nums,int target){ if (target < nums[0] || target > nums[nums.length - 1]){ return -1; } int start = 0,end = nums.length - 1; while (start <= end){ int mid = start + ((end - start) >> 1); if (nums[mid] == target){ return mid; }else if (nums[mid] < target){ start = mid + 1; }else if (nums[mid] > target){ end = mid -1; } } return -1; } }
3.移除元素
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O ( 1 ) O(1)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循环的工作。
时间复杂度：O ( n ) O(n)O(n)
空间复杂度：O ( 1 ) O(1)O(1)
package com.caq.array; import org.junit.Test; /** * 从数组中移出指定的元素，并返回移出以后数组的长度，忽略数组中超出新长度后面的元素 * 双指针法解决！（快慢指针） * * @Date 2021/12/17 22:09 * @Version 1.0 */ public class RemoveArrayElements { public static void main(String[] args) { int[] nums = {1, 2, 4, 6, 7, 11, 23}; RemoveArrayElements rae = new RemoveArrayElements(); int i = rae.removeElement1(nums, 2); System.out.println(i); } /** * 双指针解法： * 定义快指针和慢指针，当匹配到要移出的元素的时候快指针+1，慢指针不动，之后交换快指针和慢指针指向元素的位置 * 当没有匹配到的时候，慢指针和快指针就一起移动 * * @param nums * @param target * @return */ public int removeElement1(int[] nums, int target) { int slowIndex = 0; for (int fastIndex = 0; fastIndex < nums.length; fastIndex++) { if (nums[fastIndex] != target) { nums[slowIndex] = nums[fastIndex]; slowIndex++; } } return slowIndex; } }
这个不难，不明白的话可以多debug几遍
