20200403
第二問
做此题之前需要理解的时间空间复杂度
时空复杂度：
o(1), o(n), o(logn), o(nlogn)是算法的时空复杂度的表示。它不仅仅可以用于表示时间复杂度，也用于表示空间复杂度。
O后面的括号中有一个函数f(n)表示为（O(f(n))），它指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
时间复杂度O(1)：
是最低的时空复杂度，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（注释：在不考虑发生冲突的情况下）
时间复杂度为O(n)：
就代表数据量增大几倍，耗时也增大几倍。例如常见的遍历算法。
时间复杂度O(n^2)：
就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
时间复杂度O(logn)：
当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
时间复杂度O(nlogn)：
就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
原文链接：https://blog.csdn.net/BIackMamba/java/article/details/90741470
テーマ：
Given a sorted array nums, 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 by modifying the input array in-place with O(1) extra memory.
Example 1:
Given 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 returned length.
Example 2:
Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.
Clarification:
Confused why the returned value is an integer but your answer is an array?
Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.
Internally you can think of this:
// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
print(nums[i]);
}
思路：
使用快慢指针来记录遍历的坐标。
开始时这两个指针都指向第一个数字
如果两个指针指的数字相同，则快指针向前走一步
如果不同，则两个指针都向前走一步
当快指针走完整个数组后，慢指针当前的坐标加 1 就是数组中不同数字的个数
答え：
Javescript
/**
* @param {number[]} nums
* @return {number}
*/
var removeDuplicates = function(nums) {
const numsLength = nums.length;
if(numsLength == 0) return 0;
//被动指针
let slowP = 0;
for(let fastP = 0; fastP < nums.length; fastP++){
if(nums[fastP] != nums[slowP]){
slowP++;
//重构数组（用下一个指针的值覆盖重复元素）
nums[slowP] = nums[fastP];
}
}
//返回值：最后数组的长度
return slowP + 1;
};