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.
兩個坐標同時往前走刹缝，一個是非零數(shù)字的坐標邀摆，一個是整體數(shù)組的坐標净宵。
主要思路是將非零數(shù)字移到目標地點（數(shù)組的前半部分），剩下的全部是零滓技。
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.
題目分析
題目要求出去一個排序數(shù)組中重復的元素，并且不能申請額外的空間，這一類在原始數(shù)組上操作的題目還是用兩個index功舀，一個用來遍歷原始數(shù)組，一個用來記錄目標結果身弊。遍歷原始數(shù)組時辟汰，將第一個與前一個元素不同的元素存到目標位置上，當遍歷完整個數(shù)組后返回目標結果的長度
代碼
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;
}
};
一種簡潔的方法
反向思維佑刷，統(tǒng)計出現(xiàn)了多少次重復莉擒，總數(shù)減去重復次數(shù)就是非重復的次數(shù)
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.
題目分析
將一個數(shù)組中的目標元素除去，并將非目標元素放在數(shù)組前面并算出長度瘫絮。
還是兩個索引值涨冀，一個遍歷數(shù)組，另一個存非目標元素麦萤。
代碼
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.
題目分析
這道題要判斷數(shù)組中是否有重復的元素鹿鳖，可以利用set的特性，以vector中的元素初始化set壮莹，判斷兩者的長度是否相同就能判斷是否有重復的元素
代碼
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
return nums.size() > set<int>(nums.begin(), nums.end()).size();
}
};
