问题入口
时间复杂度O(n-1)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
int j = 1;
for (int i = 1; i < nums.size(); i++)
{
if(nums[i] != nums[i-1])
{
nums[j] = nums[i];
j++;
}
}
return j;
}
};时间复杂度O(nlogn)
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
/*
In a map, the elements are stored in a sorted order based on their keys.
in an unordered_map, the elements are not stored in any particular order
based on the keys.
*/
map<int, int> m;
for (int i = 0; i < nums.size(); i++)
{
m[nums[i]] = i;
}
int i = 0;
for (auto it = m.begin(); it != m.end(); it++, i++)
{
nums[i] = it->first;
}
return i;
}
};思路是map元素的特点是唯一性，每一个元素都是独一无二的。
问题是用unordered_map还是map?
C++中的“std:：map”和“std：：unordereded_map”的主要区别在于它们的底层数据结构和性能特征：
1.有序与无序：
-“std:：map”被实现为一个自平衡的二进制搜索树（通常是一个红黑树），它确保元素总是按它们的键排序。
-“std:：unordered_map”是作为哈希表实现的，它不保证元素的任何特定顺序。相反，元素是根据其键的哈希值存储在存储桶中的。2.性能：
-“std:：map”中的插入、删除和搜索操作的时间复杂度为O（logn），其中n是映射中的元素数。这是因为元素是按排序顺序存储的，这需要保持树的平衡。
-假设有一个好的哈希函数，“std:：unordereded_map”中的插入、删除和搜索操作的平均时间复杂度为O（1）。然而，在最坏的情况下，由于散列冲突，这些操作的时间复杂度可能为O（n），其中n是映射中的元素数。3.迭代：
-遍历“std:：map”中的元素将根据键按排序顺序生成它们。
-遍历“std:：unordered_map”中的元素将不按特定顺序生成它们，因为这些元素是根据其哈希值分布在存储桶中的。4.内存开销：
-与“std:：unordered_map”相比，“std：：map”通常具有更高的内存开销，因为它需要为树结构存储额外的指针。
-由于需要维护哈希表和存储桶，“std:：unordered_map”可能具有更高的内存开销。
由于map可以按照键的顺序遍历，所以选择使用map。
时间复杂度分析:
1.创建map：循环迭代“nums”向量中的每个元素，并将其插入到map中。在map中插入元素的平均时间复杂度为O（logn），这是因为map通常被实现为平衡的二进制搜索树（例如，红黑树），其中每个插入操作涉及从根遍历树到适当的叶节点，这平均需要O（logn）时间。其中n是map中元素的数量。因此，这个循环的时间复杂度是O（nlogn），第一个n是“nums”向量的大小。
2.遍历映射：循环迭代映射中的每个元素，其大小等于“nums”向量中唯一元素的数量。由于映射的大小最多等于“nums”中的唯一元素的数量，因此该循环的时间复杂度为O（n），其中n是“nums’中的唯一元件的数量。
总体而言，时间复杂性的主要因素是地图的创建，其时间复杂性为O（n log n）。因此，给定代码的总时间复杂度为O（nlogn）。
