- 双指针技巧解决数组问题：左右指针
- 双指针技巧解决数组问题：快慢指针
学习目标
- 复习Day至Day5内容
- 数组基础知识复习
- 双指针技巧解决数组问题：快慢指针
学习内容 数组基础知识
数组是具有相同类型的一组数据的集合。在Java中将数组看作为一个对象。
1. 一维数组的创建和使用一维数组实质上是一组相同类型数据的线性集合。
数组作为对象允许使用new关键字进行内存分配。在使用数组前，需要先定义数组变量所属的类型。
- 创建一维数组
- 方法1：先声明，再用new运算符进行内存分配
数组元素类型 数组名字[ ];
数组元素类型[ ] 数组名字;
int arr[]; String str[];
然后再为数组分配内存空间：
数组名字 = new 数组元素的类型[数组元素的个数]；
int arr=new int[5];
- 方法2：声明的同时为数组分配内存
int month= new int[12];
- 初始化一维数组
数组的初始化可分别初始化数组中的每个元素。
int arr1=new int[]{1,2,3,4,5};
int arr2={1,2,3,4,6};
- 使用一维数组
public class shuzu {
public static void main(String[] args) {
int Day[]=new int[] {31,28,31,30,31,30,31,31,30,31,30,31};
for(int j=0;j<12;j++) {
System.out.println((j+1)+"月有"+Day[j]+"天");
}
}
}
2. 二维数组的创建和使用
- 创建二维数组
先声明，再弄new运算符进行内存分配。
//直接位每一维分配内存空间 a=new int[2][4]; //分别为每一位分配内存空间 a=new int[2][]; a[0]=new int[2]; a[1]=new int[3];
- 初始化二维数组
type arrayname[][]={value 1,value 2,…,value n}
- 使用二维数组
public class shuzu {
public static void main(String[] args) {
int a[][]=new int[3][4];//二维数组
for(int i=0;i
for(int j=0;j
System.out.print(a[i][j]);
}
System.out.println();
}
}
}
3. 数组的基本操作
- 遍历数组
数组遍历就是获取数组中的每个元素。通常遍历数组都是用for循环来实现。遍历二维数组需要使用双层for循环，通过数组的 length 属性可获得数组的长度。
public class shuzu {
public static void main(String[] args) {
int a[][]=new int[3][4];//二维数组
for(int i=0;i
for(int j=0;j
System.out.print(a[i][j]);
}
System.out.println();
}
}
}
在遍历数组时，使用 foreach 语句会更简单。
public class Tautog{ //创建类
public static void main(String[] args){ //主方法
int arr2[][]={{4,3},{1,2}}; //定义二维数组
System.out.println("数组中的元素是："); //提示信息
int k=0; //外层循环计数器变量
for(int x[]:arr2) { //外层循环变量为一维数组
k++; //外层循环计数器递增
int j=0; //内层循环计数器
for(int e:x) { //循环遍历每一个数组元素
j++; //内存计数器递增
if(k==arr2.length&&j==x.length) { //判断变量是二维数组中的最后一个元素
System.out.println(e); //输出二维数组的最后一个元素
}
else //如果不是二维数组中的最后一个元素
System.out.print(e+"、"); //输出信息
}
}
}
}
- 填充替换数组元素
数组中的元素定义完成后，可通过Arrays类的静态方法 fill( ) 来对数组中的元素进行替换。该方法通过各种重载的形式可完成对任意类型的数组元素的替换。
- fill(int[ ] a, int value)
该方法可以将指定的 int 值分配给 int 型数组的每个元素。其中：
① a： 表示要进行元素替换的数组。
② value： 要存储数组中所有原色的值。
import java.util.Arrays;
public class Swap{
public static void main(String[] args){
int arr[]=new int[5];
Arrays.fill(A, 8);//整个数组全部填充
System.out.println("全部填充后的数组元素为：");
for(int i=0;i<5;i++){
System.out.print(A[i]+" ");
}
}
}
- fill(int[ ] a, int fromIndex, int toIndex, int value)
① a： 表示要进行元素替换的数组。
② value： 要存储数组中所有原色的值。
③ int fromIndex： 要使用指定值填充的第一个元素的索引（包括）
④ int toIndex： 要使用指定值填充的最后一个元素的索引（不包括）
import java.util.Arrays;
public class Displace{
public static void main(String[] args){
int arr[]=new int[]{45,12,2,10};
Arrays.fill(arr, 1, 2, 8);//填充结果包括起始的第一个，不包括结尾的最后一个
for(int i=0;i
System.out.print(arr[i]+" ");
}
}
}
- 数组排序
通过Arrays类的静态 sort() 方法可以实现对数组的排序。sort() 方法提供了多种重载形式，可对任意类型的数组进行升序排序。语法如下：
Arrays.sort(object)
在这里，利用 Arrays.sort(arr,Collections.reverseOrder()) 可以实现逆序排序。
import java.util.Arrays;
public class Displace{
public static void main(String[] args){
int arr[]=new int[] {1,8,3,2,5,8,9,3,5,0};
Arrays.sort(arr);//升序排列
for(int i=0;i<10;i++){
System.out.print(arr[i]+" ");
}
Integer[] arr3= {1,2,3,4,5,6,7,8,9};
System.out.println();
System.out.println("降序后的数组为元素为：");
Arrays.sort(arr3,Collections.reverseOrder());//降序排列
for(int i:arr3){
System.out.print(i+" ");
}
}
}
- 数组复制
Arrays类的 copyOf( ) 方法与 copyOfRange( ) 方法可以实现对数组的复制。copyOf( ) 方法是复制数组至指定长度，copyOfRange( ) 方法则将指定数组的指定长度复制到一个新数组中。
- copyOf( ) 方法
copyOf(arr,int newlength)
newlength 指的是复制后新数组的长度
- copyOfRange( ) 方法
copyOfRange(arr,int fromIndex, int toIndex)
import java.util.Arrays;
public class Displace{
public static void main(String[] args){
System.out.println();
System.out.println("复制后的数组为元素为：");//全局复制
int newarr1[]=Arrays.copyOf(arr, 15);
for(int i:newarr1){
System.out.print(i+" ");
}
System.out.println();
System.out.println("部分复制后的数组为元素为：");//部分复制
int newarr2[]=Arrays.copyOfRange(arr,0,5);
for(int i:newarr2){
System.out.print(i+" ");
}
}
}
- 数组查询
Arrays类的 binarySearch( ) 方法，可使用二分搜索法来搜索指定数组，以获得指定对象。该方法返回要搜索元素的索引值。binarySearch( ) 方法提供了多种重载形式，用于满足各种类型数组的查找需要。binarySearch( ) 方法有两种参数类型：
① binarySearch(Object[ ] a,Object key )
② binarySearch(Object[ ] a, int fromIndex, int toIndex, Object key )
其中 Object key为要搜索的元素。
import java.util.Arrays;
public class Displace{
public static void main(String[] args){
int arr[]=new int[] {1,8,3,2,5,8,9,3,5,0};
int index1=Arrays.binarySearch(arr, 2);//全局查询
System.out.println("arr中元素2的索引位置为："+index1);
int index2=Arrays.binarySearch(arr,0,3,2);//索引位置0到3的范围查询元素3的索引位置
System.out.println("arr中第1到4个元素中元素3的索引位置为："+index2);
}
}
4. 双指针技巧——快慢指针
-
在处理数组和链表相关问题时，双指针技巧是经常用到的，双指针技巧主要分为两类：左右指针和快慢指针。
-
所谓左右指针，就是两个指针相向而行或者相背而行；而所谓快慢指针，就是两个指针同向而行，一快一慢。
-
对于单链表来说，大部分技巧都属于快慢指针，比如链表环判断，倒数第 K 个链表节点等问题，它们都是通过一个 fast 快指针和一个 slow 慢指针配合完成任务。
在数组中并没有真正意义上的指针，但我们可以把索引当做数组中的指针，这样也可以在数组中施展双指针技巧。
- 数组问题中比较常见的快慢指针技巧，是让你原地修改数组。
- 除了让你在有序数组/链表中去重，题目还可能让你对数组中的某些元素进行「原地删除」。
学习时间
2022年6月1日
- 下午4点-下午5点
- 晚上6点-晚上8点
学习产出
- 本文档链表基础知识和基础操作
- 力扣26题，删除有序数组中的重复项
- 力扣27题，移除元素
今日刷题
26.删除有序数组中的重复项
函数签名如下：
int removeDuplicates(int[] nums);
对于原地修改：
-
如果不是原地修改的话，我们直接 new 一个 int[] 数组，把去重之后的元素放进这个新数组中，然后返回这个新数组即可。
-
但是现在题目让你原地删除，不允许 new 新数组，只能在原数组上操作，然后返回一个长度，这样就可以通过返回的长度和原始数组得到我们去重后的元素有哪些了。
-
由于数组已经排序，所以重复的元素一定连在一起，找出它们并不难。但如果毎找到一个重复元素就立即原地删除它，由于数组中删除元素涉及数据搬移，整个时间复杂度是会达到 O(N^2)。
快慢指针技巧：
- 我们让慢指针 slow 走在后面，快指针 fast 走在前面探路，找到一个不重复的元素就赋值给 slow 并让 slow 前进一步。
- 这样，就保证了 nums[0…slow] 都是无重复的元素，当 fast 指针遍历完整个数组 nums 后，nums[0…slow] 就是整个数组去重之后的结果。
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int slow = 0, fast = 0;
while (fast < nums.length) {
if (nums[fast] != nums[slow]) {
slow++;
// 维护 nums[0..slow] 无重复
nums[slow] = nums[fast];
}
fast++;
}
// 数组长度为索引 + 1
return slow + 1;
}
}
27.移除元素
- 题目要求我们把 nums 中所有值为 val 的元素原地删除，依然需要使用快慢指针技巧：
如果 fast 遇到值为 val 的元素，则直接跳过，否则就赋值给 slow 指针，并让 slow 前进一步。- 注意这里和有序数组去重的解法有一个细节差异，我们这里是先给 nums[slow] 赋值然后再给 slow++，这样可以保证 nums[0…slow-1] 是不包含值为 val 的元素的，最后的结果数组长度就是 slow。
class Solution {
public int removeElement(int[] nums, int val) {
int fast = 0, slow = 0;
while (fast < nums.length) {
if (nums[fast] != val) {
nums[slow] = nums[fast];
slow++;
}
fast++;
}
return slow;
}
}
