算法题目：目标移动

算法题目：目标移动

题目描述

给定一个数组 nums 以及一个整数 target 。
你需要把数组中等于target的元素移动到数组的最前面，并且其余的元素相对顺序不变。
你的所有移动操作都应该在原数组上面操作。

示例 1:

输入:
nums = [5, 1, 6, 1]
target=1
输出: 
[1, 1, 5, 6]
解释: 
1 是目标值，应该让所有的1在数组的最前面

示例 2:

输入:
nums = [-1, 2, 3, 5, 2, 2]
target = 2
输出: 
[2, 2, 2, -1, 3, 5]
解释: 
2 是目标值，应该让所有的 2 都在数组的最前面 

示例3：

输入:
nums = [2, 3, 4, 6]
target = 1
输出: 
[2, 3, 4, 6]
解释: 
数组中没有目标值，不需要改变原数组

思路及算法

解法：双指针
算法：双指针
解题思路：使用left，right指针，从数组尾部开始，向前遍历。

源代码

class Solution {
public:
    /**
     * @param nums: a list of integer
     * @param target: an integer
     * @return: nothing
     */
    void moveTarget(vector<int> &nums, int target) {
        // write your code here
        int count = 0;
        int left = nums.size()-1;
        int right = nums.size()-1;

        while(left >= 0){
            if(nums[left] != target){
               nums[right] = nums[left];
                right--; 
            }else{
                count++;
            }
                  
            left--;
        }


        for(int i = 0; i < count; ++i){
            nums[i] = target;
        } 
    }
};

提交结果

243 ms 时间消耗
7.77 MB 空间消耗

复杂度分析

复杂度分析
时间复杂度：O(n)
n为数组长度，需要遍历一遍数组。

空间复杂度：O(1)
原地操作不需要要额外的空间。

这是我利用C++运行提交后的结果，可能还有不同的解法哦。