要求：

1. 对数组nums原地改变，使和val不相等的元素往前走，和val相等的元素往后走，假设nums中一共有k个元素和val不相等，则最终nums的前k个元素应当都和val不等（无所谓顺序）
2. 返回nums中和val不等元素的个数 k
   • 注意：题目仅要求返回k

分析：

1. 能不能创建一个新数组，把不nums中和val不等的元素扔进去，再替换掉nums可以吗
   • 不能，如果仅仅是 nums=new_list这种方式替换，显然会因为地址问题导致检测不通过
   • 如果是先丢进new_list，再复制回来，当然可以，但很耗时间
2. 原地修改数组的最好办法：双指针
   • 双指针的两个指针角色不同。i 指针 一般用于勾住目标元素，而 j 指针 一般用于使被i勾住的目标元素和其他元素互动
   • 设和val不等的为“白色”元素，而相等的是“黑色”元素，目标即把所有白色元素向前移动
   • 基础思路：冒泡排序。
     • i指针遍历，勾住黑色元素（if nums[i] == val， then）然后j指针从i的下一位开始运行，找到离i最近的一个白色元素，互换i和j位置的元素，完成白色前移，黑色后移
     • 随后i向下一位移动，重复上述操作

图解

代码示例:

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        diff_num = 0
        for i in range(n):
            #当前i指针处为黑，将最近的白和其交换
            if nums[i] == val:
                '''
                这里必须这样if，否则会超界，
                也不能在上层循环只遍历range(n-1)，
                因为还必须检测最后一个数字
                '''
                if i<n-1: 
                    for j in range(i+1,n):
                        if nums[j] != val:
                            tp = nums[i]
                            nums[i] = nums[j]
                            nums[j] = tp
                            diff_num+=1
                            break
            else:
                diff_num+=1
        return diff_num

**优化分析：**从图解可以看到，将最近的白色元素和黑色元素交换，极有可能将黑色元素仅仅是移动到了下一位，那么这将为下一位带来冗余操作

• 可以尝试将“最远的白色”做交换，即 j 指针从nums末尾倒着走

优化前后对比：

优化前：

优化后：

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        diff_num = 0
        for i in range(n):
            #当前i指针处为黑，将最近的白和其交换
            if nums[i] == val:
                '''
                这里必须这样if，否则会超界，
                也不能在上层循环只遍历range(n-1)，
                因为还必须检测最后一个数字
                '''
                if i<n-1: 
                    **j = n-1
                    while j!=i:
                        if nums[j] != val:
                            tp = nums[i]
                            nums[i] = nums[j]
                            nums[j] = tp
                            diff_num+=1
                            break
                        j-=1**
            else:
                diff_num+=1
        return diff_num