S*******C
发帖数: 822 | 1 Given an array of integers and a number k, the majority number is the number
that occurs more than 1/k of the size of the array. Find it.
Note
There is only one majority number in the array.
Example
For [3,1,2,3,2,3,3,4,4,4] and k = 3, return 3
Challenge
O(n) time and O(k) extra space
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList nums, int k) {
// write your code
}
}
http://lintcode.com/en/problem/majority-number-iii/ | S*******C
发帖数: 822 | | m***2
发帖数: 595 | 3 ac的一个，不知道是不是最优
public class Solution {
/**
* @param nums: A list of integers
* @param k: As described
* @return: The majority number
*/
public int majorityNumber(ArrayList nums, int k) {
if (nums == null || nums.size() == 0 || k > nums.size() || k <= 0) {
return Integer.MAX_VALUE;
}
int[] value = new int[k];
int[] count = new int[k];
for (int i = 0; i < k; i++) {
count[i] = 0;
}
int n = nums.size();
for (int i = 0; i < n; i++) {
boolean startnew = true;
for (int j = 0; j < k; j++) {
if (count[j] > 0 && value[j] == nums.get(i)) {
count[j]++;
startnew = false;
break;
}
}
if (startnew) {
for (int j = 0; j < k; j++) {
if (count[j] == 0) {
value[j] = nums.get(i);
count[j] = 1;
break;
}
}
}
int minheight = Integer.MAX_VALUE;
for (int j = 0; j < k; j++) {
minheight = Math.min(minheight,count[j]);
}
for (int j = 0; j < k; j++) {
count[j] -= minheight;
}
}
int maxcount = 0;
int maxvalue = Integer.MAX_VALUE;
for (int i = 0; i < k; i++) {
if (count[i] > 0) {
int curcount = 0;
for (int j = 0; j < n; j++) {
if (nums.get(j) == value[i]) {
curcount++;
}
}
if (curcount > maxcount) {
maxcount = curcount;
maxvalue = value[i];
}
}
}
return maxvalue;
}
}
【在 S*******C 的大作中提到】
: 没人知道？
|
|
