amex的blue nile offer - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Money - 海外理财

amex的blue nile offer

amex的blue nile offer# Money - 海外理财

S*C2017-04-13 07:04

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/

l*l2017-04-13 07:04

2 楼

记得以前看过amex有过blue nile的offer，有谁用过这个offer吗？

S*C2017-04-13 07:04

3 楼

没人知道？

m*22017-04-13 07:04

4 楼

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 的大作中提到】