Each input file contains one test case. For each case, the first line contains 2 positive numbers: M (<=800) and N (<=600) which are the resolutions of the image. Then N lines follow, each contains M digital colors in the range [0, 224). It is guaranteed that the strictly dominant color exists for each input image. All the numbers in a line are separated by a space.
For each test case, simply print the dominant color in a line.
5 3 0 0 255 16777215 24 24 24 0 0 24 24 0 24 24 24
24
import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int m=in.nextInt(); int n=in.nextInt(); HashMap<String,Integer> map=new HashMap<String,Integer>(); n*=m; for(int i=0;i<n;i++){ String s=in.next(); if(map.containsKey(s)){ int value=map.get(s); map.remove(s); map.put(s, value+1); } else{ map.put(s,1); } } for(String s:map.keySet()){ if(map.get(s)>n/2.0){ System.out.println(s); } } } }
求主元素O(N),最后剩下的dom是主元素
#include
using namespace std;
int main() {
int m, n;
while (cin >> m >> n) {
long dom = -1, cnt = 0;
for (int i = 0; i<m*n; i++) {
long pixel;
cin >> pixel;
if (pixel == dom)
cnt++;//如果和dom相同,计数加一
else {
cnt--;//如果不同计数减一
if (cnt < 0) {//计数小于0,产生新的dom
dom = pixel;
cnt = 0;//重新计数
}
}
}
cout << dom << endl;
}
}
#include <iostream> #include <map> using namespace std; map<int,int> mp; //数字与出现次数映射 int main(){ int n,m,temp; cin>>m>>n; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&temp); if(mp.find(temp)==mp.end()) mp[temp]=0; //若不存在,初始化 mp[temp]++; //若已存在,数量加1 } } int k=0,max=0; //出现最多次的数字即其次数 for(map<int,int>::iterator it=mp.begin();it!=mp.end();it++){ if(it->second>max){ k=it->first; max=it->second; } } cout<<k; return 0; } //vector版 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(){ int N,M; vector<int>v; cin>>N>>M; int Index=0; for(int i=0;i<M;i++) for(int j=0;j<N;j++) { int x; scanf("%d",&x); v.push_back(x); } sort(v.begin(),v.end()); cout<<v[(v.size()+1)/2]<<endl; return 0; }
//The Dominant Color (20) #include<iostream> //#include<algorithm> #include<set> #include<vector> #include<map> using namespace std; int main(){ set<int> SET; //int record[10000000]={0}; map<int,int> mapRecord; int m,n;cin>>m>>n; int temp;int cnt=0; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin>>temp;cnt++; map<int,int>::iterator iter=mapRecord.find(temp); if(iter!=mapRecord.end())iter->second++;//-------------------!!! else mapRecord.insert(pair<int,int>(temp,1)); SET.insert(temp); } } for(set<int>::iterator it=SET.begin();it!=SET.end();it++){ if(mapRecord.find(*it)->second>cnt/2)cout<<*it; } return 0; }
#include <iostream> using namespace std; #define INT_MAX 16777218 int buf[INT_MAX]={0}; int main() { int m,n; cin >> m >> n; for (int i=0; i<m*n; i++) { int val; cin >> val; buf[val]++; } for (int j=0; j<INT_MAX; j++) { if (buf[j] > m*n/2) cout << j << endl; } return 0; }
#include<iostream>
#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<set>
#include<stack>
#include<cstring>
#include<string>
#include<algorithm>
#include<cstdlib>
using namespace std;
int m, n;
map<int, int> mp;
int main()
{
int maxx = -(1 << 24);
int ans = 0,num;
cin >> m >> n;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
{
cin >> num;
mp[num]++;
if (mp[num] > maxx)
{
maxx = mp[num];
ans = num;
}
}
cout << ans << endl;
system("pause");
return 0;
}
/* 3 2 4502761 4502761 4502761 4502761 7340438 3208719 */ //不用map数组,两两抵消 #include <cstdio> int main(int argc, char const *argv[]) { int n, m; scanf("%d%d", &n, &m); int num; int count = 1, ans = -1; for(int i = 0; i < n * m; i++){ scanf("%d", &num); if(ans != num){ count--; }else{ count++; } if(count == 0){ ans = num; count++; } } printf("%d\n", ans); return 0; }
#include <bits/stdc++.h> using namespace std; int main() { int m, n; while (cin >> m >> n) { ios::sync_with_stdio(false); vector<long long int>colors; for (int i = 0; i < m * n; ++i) { long long int color; cin >> color; colors.emplace_back(color); } long long int domain = colors[0]; int count = 1; for (int i = 1; i < colors.size(); ++i) { if (domain == colors[i]) { count++; } else if (--count < 0) { domain = colors[i]; count=1; } } cout << domain << endl; } }
占了好大的内存呀😅 #include<bits/stdc++.h> using namespace std; const int Max=1e8; int Hashtable[Max]; int main() { ios::sync_with_stdio(0); int n,m,Max=0,ans; cin>>n>>m; int x; for(int i=0; i<n; i++) { for(int j=0; j<m; j++) { cin>>x; Hashtable[x]++; if(Hashtable[x]>Max) { Max=max(Max,Hashtable[x]); ans=x; } } } cout<<ans<<endl; }
m, n = map(int, input().split()) clr = {} # 字典是O(1),比list要快很多,把存储结构换成字典 th = m * n / 2 th1 = m * n while len(clr) != th1: cur = input().split() for i in cur: if clr.get(i, -1) != -1: clr[i] += 1 else: clr[i] = 1 l = sorted(clr.items(), key=lambda x: x[1], reverse=True) if l[0][1] > th: print(l[0][0]) break # 原来的,最后两个测试点会超时 # m, n = map(int, input().split()) # clr = [] # th = m * n / 2 # th1 = m * n # while len(clr) != th1: # # cur = list(map(int, input().split())) # cur = [int(i) for i in input().split()] # clr.extend(cur) # tmp_s = set(cur) # cnt = [(clr.count(i), i) for i in tmp_s] # if max(cnt)[0] > th: # print(max(cnt)[1]) # break
//The Dominant Color (20分) #include <iostream> (720)#include <map> using namespace std; int n, m, maxcolor = 0; map<int, int> arrays; int main() { scanf("%d %d", &m, &n); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int color; scanf("%d", &color); arrays[color]++; } } for (map<int, int>::iterator it = arrays.begin(); it != arrays.end(); it++) { if (it->second > arrays[maxcolor] && it->second > (n * m) / 2) maxcolor = it->first; } printf("%d", maxcolor); }
#include<iostream> #include<stdlib.h> using namespace std; int main() { map<int, int> p; int len = 0, wid = 0, tem = 0; cin >> len >> wid; for (int i = 0; i < len*wid; i++) { scanf("%d",&tem); p[tem]++; if (p[tem] > len*wid / 2)break; } cout << tem<<endl; system("pause"); return; }