【LeetCode】27. Remove Element

问题描述

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

简单点讲，就是给定一个数组和一个数k，返回删除数组里所有的k之后数组长度。要求是不能新增数组，但可以交换元素位置。

思路

从最后一个数开始从后往前遍历数组，使用一个指针index记录当前**不为数k**的数的位置，遍历时，如果当前数是k，那么指针前移；如果当前数不是k，并且当前的index不是val，那么交换当前数和index指向的数，同时index前移。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
    	if(nums.size()==0) return 0;
        int index = nums.size()-1;
        if(index <= 0&&nums[index]==val) {
        	return 0;
        }
        for(int i=index;i>=0;i--){
        	if(nums[i]==val&&nums[index]!=val){
        		swap(nums, index, i);
	        	index--;
        	} else if(nums[i]==val) {
	        	index--;
	        }
        }
        return index+1;
    }
    
    void swap(vector<int>& nums, int i, int j) {
    	int t = nums[i];
    	nums[i] = nums[j];
    	nums[j] = t;
    }
};