//做的时候没想到中间值的方法,使用map的方法如下 import java.util.Scanner; import java.util.Map; import java.util.TreeMap; import java.util.Map.Entry; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); while(sc.hasNext()){ Map<Integer,Integer> map = new TreeMap<>(); String[] strs = sc.nextLine().split(" "); for(int i=0;i<strs.length;i++){ int s = Integer.valueOf(strs[i]); if(map.containsKey(s)){ map.put(s,map.get(s)+1); }else{ map.put(s,1); } } for(Map.Entry<Integer,Integer> entry : map.entrySet()){ if(entry.getValue() >= strs.length/2){ System.out.println(entry.getKey()); } } } } }
import java.util.*; /** * 剑指offer原题 * * @author 何嘉龙 * */ public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { String str = in.nextLine(); String[] strs = str.split(" "); int[] arr = new int[strs.length]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.valueOf(strs[i]); } int num = arr[0]; int count = 0; for (int j = 1; j < arr.length; j++) { if (arr[j] == num) { count++; } else if (count > 0) { count--; } else { num = arr[j]; } } System.out.println(num); } } }
O(n)~ #include<stdio.h> #include<stdlib.h> int main() { int a[105]; int i = 0; while(~scanf("%d",&a[i])){ i++; } int num = a[0]; int cnt = 0; for(int j = 1 ; j < i ; ++j){ if(a[j] == num){ cnt++; }else if(cnt>0){ cnt--; }else{ num = a[j]; } } printf("%d\n", num); return 0; }
//O(n)思想:因为要找过半的数,用一个变量count记录读取每个变量变化的次数, //一个变量temp记录可能过半的数,先让count=1,然后让temp=vec[0], //然后往后遍历一遍,碰到和temp相同的数就给count++,否则就count-- //如果,count变成0,就让temp=vec[i](vec数组遍历过程当前值),并让count=1 //如此遍历一遍,因为有一个数过半,所以temp最后肯定存储的是过半的数 #include <bits/stdc++.h> using namespace std; int main(){ int n; vector <int> vec; while(cin >> n) vec.push_back(n); int count = 1; int temp = vec[0]; for(int i = 1; i < vec.size(); ++i){ if(vec[i] == temp) count++; else count--; if(count == 0) temp = vec[i], count++;//(逗号表达式,懒得写大括号) } cout << temp << endl; return 0; }
import java.util.Arrays; import java.util.Scanner; public class Main { //如果这个数出现的次数超过一半 排序后数组中间的数必定是它 // public static int getCountHalfLen(int[] arr){ // Arrays.sort(arr); // return arr[arr.length/2]; // } public static int getCountHalfLen(int[] arr){ int[] count = new int[arr.length]; //count[i]表示索引为i出现的次数,统计每个数出现的次数 for (int i = 0; i < count.length; i++) { for (int j = 0; j < count.length; j++) { if(arr[i] == arr[j]) count[i]++; } } for (int i = 0; i < count.length; i++) { if(count[i] >= (arr.length + 1)/2) return arr[i]; } return 0; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); String dataStr = sc.nextLine(); String[] split = dataStr.split(" "); int[] arr = new int[split.length]; for (int i = 0; i < arr.length; i++) { arr[i] = Integer.parseInt(split[i]); } System.out.println(getCountHalfLen(arr)); } }
publicstaticvoidmain(String[] args) {Scanner sc = newScanner(System.in);String str = sc.nextLine();String [] arrays = str.split(" ");intnTime,id = Integer.MIN_VALUE;for(inti= nTime = 0;i<arrays.length;i++){if(nTime == 0){id = Integer.valueOf(arrays[i]);nTime = 1;}else{if(id == Integer.valueOf(arrays[i]) ){++ nTime;}else{-- nTime;}}}System.out.println(id);sc.close();}
方法一 :枚举法,时间复杂度O(n2)
这样时间复杂度取决于排列方法 + 遍历判断次数是否大于一半。
时间复杂度:排列O(nlogn)+遍历O(n) = O(n)
代码略…
/*涉及到奇偶问题以及两个数各占一半的问题*/ #include <bits/stdc++.h> using namespace std; int main() { int a[100] = { 0 }, b[100] = { 0 }; int n, i = 0, j, num = 0, temp; while (cin >> n) { b[i++] = n; a[n]++; } int f=i; for (j = 0; j < i; j++) { if(i%2==1) //总数为奇数的情况,不存在两个数各占一半的状况 { if (a[b[j]] > i / 2)//重复次数大于长度一半 { cout << b[j] << endl; break;//如果重复次数大于长度一半,那么只能有一个数满足,所以直接跳出。 } } else//总数为偶数的情况,存在各占一半的情况 { bool flag = true; if (a[b[j]] > i / 2)//重复次数大于长度一半 { cout << b[j] << endl; break;//如果重复次数大于长度一半,那么只能有一个数满足,所以直接跳出。 } else if (a[b[j]] == i / 2 )//重复次数等于长度一半 { cout << b[j] << endl; for(int k=0;k<f;k++) { if(b[k] != b[j]) { if(a[b[k]] == i / 2) { cout<<b[k] << endl; flag=false; break; } else { flag=false; break; } } } if(flag == false) { break; } } } } }
/*看了几页发现竟然没有人用STL的set或者map去做这道题目,开数组去做这道题目大概率不好, 一旦输入数字较大那扫描的时候就比较耗时;而且看了好几个人的实现,利用cnt和temp去 统计的方法在面对一些零散的排列的时候都有可能出现问题,例如这些解法评论里的 2 3 4 3 5这种排列往往得到的就是最后一个数5而不是3.当然排序的方法很粗暴,个人很喜欢hhhhh, 但是还是想写一个更简单的,这道题用map去实现,利用键值对的方法比较清晰,而且不需要开很大 的数组,左值存储数字,右值存储该数字的出现次数,最后用一个迭代器判断右值就OK了呀*/#include <bits/stdc++.h> using namespace std;int main() { int n,cnt=0; map <int,int> num; while(cin >> n) { num[n]++; cnt++; } for(map<int,int>::iterator it=num.begin();it!=num.end();it++) { if((it->second)>=(cnt/2)) cout << it->first; } return 0; }