Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

两个坐标同时往前走，一个是非零数字的坐标，一个是整体数组的坐标。
主要思路是将非零数字移到目标地点（数组的前半部分），剩下的全部是零。

void moveZeroes(vector<int>& nums) {
        int j=0;
        for (int i=0; i<nums.size(); i++) {
            if (nums[i] != 0) {
                nums[j] = nums[i];
                j++;
            }
        }
        for ( ; j<nums.size() ; j++) {
            nums[j] = 0;
        }
        return;
    }

Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

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

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

题目分析

题目要求出去一个排序数组中重复的元素，并且不能申请额外的空间，这一类在原始数组上操作的题目还是用两个index，一个用来遍历原始数组，一个用来记录目标结果。遍历原始数组时，将第一个与前一个元素不同的元素存到目标位置上，当遍历完整个数组后返回目标结果的长度

代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int len = nums.size();
        int i = 0;
        int res = 0;
        while (i < len) {
            nums[res] = nums[i];
            while (nums[i+1] == nums[i] && i < len) {
                i++;
                if (i == len){
                    res++;
                    return res;
                }
            }
            i++;
            res++;
        }
        return res;
    }
};

一种简洁的方法

反向思维，统计出现了多少次重复，总数减去重复次数就是非重复的次数

int count = 0;
for(int i = 1; i < n; i++){
    if(A[i] == A[i-1]) count++;
    else A[i-count] = A[i];
}
return n-count;

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.

题目分析

将一个数组中的目标元素除去，并将非目标元素放在数组前面并算出长度。
还是两个索引值，一个遍历数组，另一个存非目标元素。

代码

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int j = 0;
        for (int i=0; i<len; i++) {
            if(nums[i] != val) {
                nums[j++] = nums[i];
            }
        }
        return j;
    }
};

Contains Duplicate

Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.

题目分析

这道题要判断数组中是否有重复的元素，可以利用set的特性，以vector中的元素初始化set，判断两者的长度是否相同就能判断是否有重复的元素

代码

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        return nums.size() > set<int>(nums.begin(), nums.end()).size();        
    }
};