【经典算法】LeetCode 27. 移除元素(Java/C/Python3/Go实现含注释说明,Easy)

一、背景与问题

LeetCode 27题"移除元素"是数组操作的经典问题，其核心要求是：给定一个数组和一个目标值，原地移除所有等于目标值的元素，并返回新数组的长度。该问题看似简单，但背后蕴含着对算法效率、内存管理、数据结构特性的深刻理解。

该问题的典型应用场景包括：

数据清洗时的元素过滤
数组压缩时的冗余元素删除
需要保持原地修改特性的算法设计

在实际开发中，该问题常出现在需要处理动态数组的场景，例如：

实时数据流处理系统
内存敏感的嵌入式系统
需要高效内存管理的缓存系统

二、基本原理

该问题的解决方案基于双指针法（Two Pointers），其核心思想是通过两个指针分别表示当前处理的位置和遍历的位置，通过一次遍历完成元素的筛选。

算法流程如下：

初始化两个指针：slow（指向当前已处理的最后一个位置）和fast（遍历数组）
遍历数组时，若fast指向的元素不等于val，则将其复制到slow的位置，并slow后移
遍历完成后，slow即为新数组的长度

该算法的时间复杂度为O(n)，空间复杂度为O(1)，满足题目对原地修改的要求。

三、环境准备

不同语言的实现需要不同的环境配置：

Java

JDK 1.8+
IDE：IntelliJ IDEA 或 Eclipse
无需额外依赖

C

GCC 编译器
编译命令：gcc -o remove_element remove_element.c

Python3

Python 3.8+
无需额外依赖

Go

Go 1.20+
IDE：VS Code + Go插件

四、核心实现

Java实现

public class RemoveElement {
    public static int removeElement(int[] nums, int val) {
        int slow = 0; // 慢指针，指向当前已处理的最后一个位置
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast]; // 将有效元素复制到slow位置
            }
        }
        return slow; // slow即为新数组的长度
    }

    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3};
        int val = 3;
        int newLength = removeElement(nums, val);
        System.out.println("新长度: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }
}

关键代码解释：

slow指针始终指向当前已处理的最后一个有效元素的下一个位置
通过nums[slow++] = nums[fast]实现原地修改
最终返回slow作为新长度

C实现

#include <stdio.h>
#include <stdlib.h>

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0; // 慢指针
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast]; // 原地修改
        }
    }
    return slow;
}

int main() {
    int nums[] = {3, 2, 2, 3};
    int val = 3;
    int newLength = removeElement(nums, 4, val);
    printf("新长度: %d\n", newLength);
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

关键点说明：

C语言数组是固定长度的，直接操作原数组
slow指针的递增操作确保内存连续性
返回的slow值即为新数组长度

Python3实现

def remove_element(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]  # 原地修改
            slow += 1
    return slow

# 测试用例
nums = [3, 2, 2, 3]
val = 3
new_length = remove_element(nums, val)
print(f"新长度: {new_length}")
print("新数组:", nums[:new_length])

特性说明：

Python列表是动态数组，可自动调整大小
通过切片nums[:new_length]获取新数组
无需显式处理内存管理

Go实现

package main

import "fmt"

func removeElement(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast] // 原地修改
            slow++
        }
    }
    return slow
}

func main() {
    nums := []int{3, 2, 2, 3}
    val := 3
    newLength := removeElement(nums, val)
    fmt.Printf("新长度: %d\n", newLength)
    fmt.Println("新数组:", nums[:newLength])
}

特性说明：

Go的切片是引用类型，修改会直接影响原数组
nums[:newLength]获取新数组的视图
切片的动态特性简化了内存管理

五、完整案例

多语言对比案例

输入：

数组：[3, 2, 2, 3, 4, 5, 3]
目标值：3

预期输出：

新长度：4
新数组：[2, 2, 4, 5]

Java实现

public class RemoveElementDemo {
    public static void main(String[] args) {
        int[] nums = {3, 2, 2, 3, 4, 5, 3};
        int val = 3;
        int newLength = removeElement(nums, val);
        System.out.println("新长度: " + newLength);
        for (int i = 0; i < newLength; i++) {
            System.out.print(nums[i] + " ");
        }
    }

    public static int removeElement(int[] nums, int val) {
        int slow = 0;
        for (int fast = 0; fast < nums.length; fast++) {
            if (nums[fast] != val) {
                nums[slow++] = nums[fast];
            }
        }
        return slow;
    }
}

Python3实现

def remove_element(nums, val):
    slow = 0
    for fast in range(len(nums)):
        if nums[fast] != val:
            nums[slow] = nums[fast]
            slow += 1
    return slow

nums = [3, 2, 2, 3, 4, 5, 3]
val = 3
new_length = remove_element(nums, val)
print(f"新长度: {new_length}")
print("新数组:", nums[:new_length])

C实现

#include <stdio.h>

int removeElement(int* nums, int numsSize, int val) {
    int slow = 0;
    for (int fast = 0; fast < numsSize; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

int main() {
    int nums[] = {3, 2, 2, 3, 4, 5, 3};
    int val = 3;
    int newLength = removeElement(nums, 7, val);
    printf("新长度: %d\n", newLength);
    for (int i = 0; i < newLength; i++) {
        printf("%d ", nums[i]);
    }
    return 0;
}

六、源码解析

以Java实现为例，逐行分析关键代码：

int slow = 0;：初始化慢指针，指向当前已处理的最后一个有效元素的下一个位置
for (int fast = 0; fast < nums.length; fast++)：快指针遍历整个数组
if (nums[fast] != val)：判断当前元素是否需要保留
nums[slow++] = nums[fast];：将有效元素复制到慢指针位置，并递增慢指针
return slow;：返回慢指针位置作为新长度

该实现的关键在于：

通过一次遍历完成元素筛选
原地修改保证空间复杂度O(1)
顺序处理确保内存连续性

七、进阶使用

1. 高效内存管理

在C语言中，可以结合realloc实现动态数组调整：

#include <stdio.h>
#include <stdlib.h>

int removeElement(int* nums, int* size, int val) {
    int slow = 0;
    int new_size = *size;
    for (int fast = 0; fast < *size; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    int* new_nums = (int*)realloc(nums, slow * sizeof(int));
    if (new_nums) {
        *size = slow;
        return slow;
    }
    return -1;
}

2. 并发场景下的应用

在Go语言中，可以结合goroutine实现并发处理：

func removeElementConcurrent(nums []int, val int) int {
    slow := 0
    for fast := 0; fast < len(nums); fast++ {
        if nums[fast] != val {
            nums[slow] = nums[fast]
            slow++
        }
    }
    return slow
}

func main() {
    nums := []int{3, 2, 2, 3, 4, 5, 3}
    val := 3
    newLength := removeElementConcurrent(nums, val)
    fmt.Printf("新长度: %d\n", newLength)
    fmt.Println("新数组:", nums[:newLength])
}

3. 异常处理增强

在Java中添加边界检查：

public static int removeElement(int[] nums, int val) {
    if (nums == null) {
        return 0;
    }
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow++] = nums[fast];
        }
    }
    return slow;
}

八、性能与工程实践

1. 性能分析

时间复杂度：O(n)（一次遍历）
空间复杂度：O(1)（原地修改）
优化方向：避免不必要的内存拷贝

2. 高效实现技巧

避免使用额外的数组创建
利用语言特性（如Python的切片）
在C语言中使用realloc动态调整内存

3. 安全考量

避免数组越界访问
在C/C++中注意内存释放
在Go中注意切片的容量限制

4. 异常处理

检查输入参数有效性
处理空数组情况
在多线程环境中处理并发访问

九、常见问题与踩坑

1. 常见错误

错误示例：

public static int removeElement(int[] nums, int val) {
    int slow = 0;
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != val) {
            nums[slow] = nums[fast];
            slow++; // 错误：先递增再赋值
        }
    }
    return slow;
}

问题分析：

指针递增顺序错误导致元素覆盖
造成部分元素丢失

改进方案：

nums[slow++] = nums[fast]; // 先赋值再递增

2. 常见陷阱

陷阱1：忽略数组长度变化

int newLength = removeElement(nums, 7, val);
printf("新长度: %d\n", newLength);
for (int i = 0; i < newLength; i++) {
    printf("%d ", nums[i]);
}

陷阱2：在Python中修改列表长度

nums = [3, 2, 2, 3]
val = 3
slow = 0
for fast in range(len(nums)):
    if nums[fast] != val:
        nums[slow] = nums[fast]
        slow += 1
print("新长度:", slow)
print("新数组:", nums[:slow]) # 正确切片

十、最佳实践

1. 推荐方案

使用双指针法实现O(n)时间复杂度
原地修改保证空间效率
避免创建额外数组
在多语言中注意内存管理差异

2. 实际应用场景

数据清洗：过滤无效元素
数组压缩：减少内存占用
缓存管理：动态调整数据结构

3. 不推荐使用场景

不需要原地修改时
数据结构允许使用额外空间时
需要保持元素顺序时（需额外处理）

4. 优化建议

在C语言中使用realloc动态调整内存
在Go中利用切片特性
在Python中利用列表切片操作

十一、总结

LeetCode 27题"移除元素"作为经典算法问题，其核心在于理解双指针法的原理和应用。通过不同语言的实现，我们可以看到：

Java/C需要显式管理内存
Python/Go利用语言特性简化实现
无论哪种语言，都遵循相同的算法逻辑

在实际开发中，该算法适用于需要高效内存管理的场景，但在不需要原地修改或需要保持元素顺序时，应选择更适合的方案。通过深入理解算法原理，我们可以更好地应对各种数据处理场景，提升代码质量和运行效率。

【经典算法】LeetCode 27. 移除元素(Java/C/Python3/Go实现含注释说明,Easy)

【经典算法】LeetCode 27. 移除元素(Java/C/Python3/Go实现含注释说明,Easy)

一、背景与问题

二、基本原理

三、环境准备

Java

C

Python3

Go

四、核心实现

Java实现

C实现

Python3实现

Go实现

五、完整案例

多语言对比案例

Java实现

Python3实现

C实现

六、源码解析

七、进阶使用

1. 高效内存管理

2. 并发场景下的应用

3. 异常处理增强

八、性能与工程实践

1. 性能分析

2. 高效实现技巧

3. 安全考量

4. 异常处理

九、常见问题与踩坑

1. 常见错误

2. 常见陷阱

十、最佳实践

1. 推荐方案

2. 实际应用场景

3. 不推荐使用场景

4. 优化建议

十一、总结

评论已关闭

推荐阅读