输入包含两行,第一行输入包含两个整数n和k,第二行包含n个整数,代表数组arr。
输出所有出现次数大于n/k的数,如果没有这样的数,请输出”-1“。
7 7 1 2 3 1 2 3 4
1 2 3
4 1 1 1 2 3
-1
时间复杂度,额外空间复杂度。
#include <bits/stdc++.h> using namespace std; int main(){ int n, k, x; scanf("%d%d", &n, &k); map<int, int> M; for(int i=0;i<n;i++){ scanf("%d", &x); M[x]++; } bool flag = false; for(auto &p: M){ if(p.second > n/k){ flag = true; printf("%d ", p.first); } } if(!flag) puts("-1"); return 0; }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int k = scanner.nextInt(); int[] arr = new int[n]; for(int i=0;i<n;i++){ arr[i] = scanner.nextInt(); } Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i=0;i<n;i++) { if(map.containsKey(arr[i])) { map.put(arr[i], map.get(arr[i])+1); }else { if(map.size() == k-1) { minusMapEle(map); }else { map.put(arr[i], 1); } } } Map<Integer, Integer> resMap = new HashMap<Integer, Integer>(); for(int i=0;i<n;i++) { if(resMap.containsKey(arr[i])) { resMap.put(arr[i], resMap.get(arr[i])+1); }else { if(map.containsKey(arr[i])) { resMap.put(arr[i], 1); } } } int count=0; for(Map.Entry<Integer, Integer> entry:resMap.entrySet()) { int value = entry.getValue(); if(value > n/k) { count++; System.out.print(entry.getKey() + " "); } } if(count==0) System.out.println(-1); } public static void minusMapEle(Map<Integer, Integer> map) { List<Integer> removeList = new ArrayList<Integer>(); for(Map.Entry<Integer, Integer> entry:map.entrySet()) { int value = entry.getValue(); entry.setValue(value-1); if(value==1) { removeList.add(entry.getKey()); } } for(Integer i:removeList) { map.remove(i); } } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.HashMap; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] params = br.readLine().split(" "); int n = Integer.parseInt(params[0]), k = Integer.parseInt(params[1]); String[] strArr = br.readLine().split(" "); long[] arr = new long[n]; HashMap<Long, Integer> counter = new HashMap<>(); for(int i = 0; i < n; i++) { arr[i] = Long.parseLong(strArr[i]); counter.put(arr[i], counter.getOrDefault(arr[i], 0) + 1); } boolean flag = false; for(long key: counter.keySet()){ if(counter.get(key) > n / k) { flag = true; System.out.print(key + " "); } } if(!flag) System.out.println(-1); } }
import java.util.*; import java.util.Map.Entry; public class Main { public static void main(String[] args) { Scanner sc =new Scanner(System.in); int n=sc.nextInt(); int k=sc.nextInt(); int []arr=new int[n]; HashMap<Integer, Integer> map =new HashMap<>(); for (int i=0;i<n;i++){ arr[i]=sc.nextInt(); if (map.size()<k){ if (map.containsKey(arr[i])){//如果map中已经有arr[i],则将其次数加1 map.put(arr[i],map.get(arr[i])+1); }else{//如果map中没有 map.put(arr[i],1); } } if(map.size()==k ){//当map中出现k个不同的数字时,则其个数减1,如果减1之后为0,则直接删除 Iterator<Entry<Integer, Integer>> it = map.entrySet().iterator();//因为需要在遍历的过程中,删除元素,所以用迭代器 while (it.hasNext()) { Entry<Integer, Integer> entry = it.next(); if (entry.getValue() == 1) {//减1之后,为0 it.remove();// 使用迭代器的remove()方法删除元素 }else{ map.put(entry.getKey(),entry.getValue()-1); } } } } for (Entry<Integer,Integer> set: map.entrySet()){ map.put(set.getKey(),0); } boolean flag=false; for (int i = 0; i <n; i++) { if (map.containsKey(arr[i])){ map.put(arr[i],map.get(arr[i])+1);//重新统计map中剩余元素,出现的次数是否满足要求 if (map.get(arr[i])>n/k){ flag=true; System.out.print(arr[i]+" "); map.remove(arr[i]);//如果已经输出一个,则可以直接移除 } } } if (flag==false){//没有打印-1 System.out.println(-1); } } }
#include<bits/stdc++.h> using namespace std; void process(map<int,int>& mp) { vector<int>tmp; for(auto& item : mp) { // 找到所有计数为一的键 if(item.second==1) tmp.push_back(item.first); item.second -= 1; } // 删除 for(auto i : tmp) mp.erase(i); } int main() { int n,k; cin>>n>>k; //k = n/k; vector<int>v(n); for(int i=0;i<n;++i) cin>>v[i]; // 存所有候选数字 map<int,int>mp; for(int i=0;i<n;++i) { if(mp.find(v[i])!=mp.end()) ++mp[v[i]]; else { // 消去k个不同的候选 if(mp.size()==k-1) process(mp); // 不满k个,继续插入 else mp.insert(make_pair(v[i],1)); } } // 判断剩下的候选是否为所求 map<int,int>ans; for(int i=0;i<n;++i) { if(mp.count(v[i])) { if(ans.count(v[i])) ++ans[v[i]]; else ans.insert(make_pair(v[i],1)); } } bool find = false; for(auto item : ans) if(item.second>n/k) { cout<<item.first<<" "; find = true; } if(!find) cout<<-1<<endl; return 0; }
#include<iostream> #include<map> using namespace std; int main() { int n,k; while (cin >> n >> k) { int temp=0; map<int, int>v; v.clear(); for (int i = 0; i < n; i++) { cin >> temp; v[temp]++; } int p = n / k; bool flag = false; for(auto ptr=v.begin();ptr!=v.end();ptr++) { if(ptr->second>p) { cout<<ptr->first<<" "; flag = true; } } if(flag) { cout<<endl; return 0; } cout<<"-1"<<endl; } return 0; }把上一个题目的代码稍微改动了几行....懒得新申请空间直接加了一个判定