第二题
题目:元素消除
给定一个整数数组nums,同时给定一个整数interval。指定数组nums中的某个元素作为起点,然后以interval为间隔递增,如果递增的数(包含起点)等于nums中的元素,则将数组nums中对应的元素消除,返回消除元素最多的起点元素。如果消除的元素同样多,则返回最小的起点元素。
输入描述
第一行输入整数数组的长度n
第二行输入长度为n的整数数组nums
第三行输入整数interval1 <= n <= 10^5
0 <= nums[i] <= 10^8
0 <= interval <= 10^5
输出描述
起点元素的最小值。
样例输入一
6 4 5 7 1 1 2 3
样例输出一
1
说明
输入给定的间隔为3,如果以元素1为起点,则可以消除1, 4, 7, 10,…这些元素,因此,我们可以消除给定数组中的4, 7, 1, 1这4个元素,以其他元素为起点也没有办法消除更多元素了,因此返回1。
样例输入二
5 4 5 7 1 2 50
样例输出二
1
说明
输入给定的间隔为50,如果以元素1为起点,则可以消除1,51,101这些元素,因此,我们可以消除给定数组中的1这个元素,同理,如果以2为起点,则可以消除2,52,102这些元素,因此,我们可以消除给定数组中的2这个元素,以此类推,无论以哪个元素作为起点,都只能消除1个元素,因此返回最小的起点元素1。
思路:
由于给定间隔interval是固定的,很容易想到符合条件的数之间是同余的关系。注意到数据范围是1e6,那么就可以使用unordered_map实现的哈希表。
处理输入,然后对于每个序列中的数,将nums[i]对interval取模后的数记为t,利用哈希表统计t的数值(即余数同为t的数的个数)。更新anscnt=max(anscnt,hashmap[t])。
最后扫描一遍,如果某个数余数的哈希值为anscnt且该数的大小小于ans,则更新ans。(题目要求所有同余的数要输出最小的数)。
我用了ios_base::sync_with_stdio(false);和cin.tie(NULL);语句来提高cin和cout的速度,确保输入格式统一。
ios_base::sync_with_stdio(false);的作用:C++标准库默认会同步C++的标准I/O和C的标准I/O。关闭同步之后‘cin’和‘cout’将不再与C标准库的‘scanf’和‘printf’同步,可以减少同步开销,从而提高性能。
cin.tie(NULL);的作用:默认情况下‘cin’与‘cout’是绑定的,接触绑定后,‘cin’和‘cout’将不再相互依赖,减少不必要的刷新操作,从而提高性能。
奇怪的问题:用不用cout.tie(NULL);?
回答:‘cout’通常不需要解除与其他流的绑定,因为‘cout’的输出操作不依赖于‘cin’的刷新。
代码:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int Work(int&n,vector<int>&nums,int&k){ 4 unordered_map<int,int>hashmap; 5 int anscnt=0,ans=1e9; 6 for(int i=1;i<=n;i++){ 7 int t=nums[i]%k; 8 hashmap[t]++; 9 anscnt=max(anscnt,hashmap[t]); 10 } 11 for(int i=1;i<=n;i++) 12 if(hashmap[nums[i]%k]==anscnt) 13 ans=min(ans,nums[i]); 14 return ans; 15 } 16 int main(){ 17 ios_base::sync_with_stdio(false); 18 cin.tie(NULL); 19 int n; 20 cin>>n; 21 vector<int>nums(n+1); 22 for(int i=1;i<=n;i++) cin>>nums[i]; 23 int interval; 24 cin>>interval; 25 cout<<Work(n,nums,interval); 26 return 0; 27 }
by:AlenaNuna
标签:0828,笔试,cout,nums,int,元素,cin,华为,消除 From: https://www.cnblogs.com/AlenaNuna/p/18404488