vector

vector索引

vector只有在指定长度时,才能用下标索引的方法修改元素

vector<int> a(10);

int main(){
	int n = 2;
	for(int i=0;i<n;i++){
		cin >> a[i];
	}
	for(auto p = a.begin();p != a.end(); p++){
		cout << *p;
	}
	return 0;
} 

下标访问

for(int i = 0; i < 5; i++)
	cout << vi[i] << " ";

迭代器访问
迭代器类似指针，迭代器在vector中就是充当指针的作用

vector<int>::iterator it;
for(it = vi.begin(); it != vi.end();it ++)
	cout << *it << " ";

返回首尾部的元素

1. front() 返回第一个元素
2. back() 返回最后一个元素

vector 插入/删除 元素

1. 在尾部进行插入/删除
   • push_back()
   • pop_back()
2. 指定位置的插入/删除
   • insert() c.insert(it, x) : 向任意迭代器it插入一个元素x ，O(N)
   • erase() c.erase(first,last) 删除[first,last)的所有元素，first,last都为迭代器指针 ，O(N)

vector去重

1. 先进行 sort() 排序，这样重复元素就会堆一起了
2. 调用 unique() 函数将相邻且重复 （因此要先排序） 的元素放到vector的尾部 然后返回指向第一个重复元素的迭代器
3. 再用erase函数擦除从迭代器所指元素到最后元素的所有的元素

sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());

vector截取

void assign(const_iterator first,const_iterator last); //两个指针，分别指向开始和结束的地方

//通过vector的迭代器截取数组
auto first = a.begin() + 1;
auto end = a.end()-1;
a.assign(first,end);

第k小数

寻找序列第k小的值 nth_element(beg, nth, end)
nth_element(a,a+k,a+n)，函数只是把下标为k的元素放在了正确位置
求第k大时,我们可以转化成求第n+1-k小，此时下标应该是n - k,所以为 nth_element(a,a+n-k,a+n) 也可以用cmp自定义比较函数，greater<int>()

nth为一个迭代器，指向序列中的一个元素。第n小的值恰好在nth位置上

执行nth_element()之后，序列中的元素会围绕nth进行划分：nth之前的元素都小于等于它，而之后的元素都大于等于它

哈希表 + vector

1. unordered_map<int,int> st; 哈希表统计数据
2. vector<pair<int,int>> a; vector的sort来排序

class Solution {
public:
    unordered_map<int,int> st; //哈希表统计数据
    vector<pair<int,int>> a; //vector的sort来排序
    vector<int> topKFrequent(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        for(int i=0;i<n;i++){
            st[nums[i]] ++;
        }
        auto it = st.begin();
        while(it != st.end()) {
            a.push_back({it->second,it->first});
            it ++;
        }
        sort(a.begin(),a.end());
        for(int i = a.size()-1;i>=0;i--){
            if(k == 0) break;
            res.push_back(a[i].second);
            k--;
        }
        return res;
    }
};