My code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class Solution {
public List<Integer> majorityElement(int[] nums) {
if (nums == null)
return null;
List<Integer> result = new ArrayList<Integer>();
if (nums.length == 0)
return result;
if (nums.length == 1) {
result.add(nums[0]);
return result;
}
int upLimit = nums.length / 3;
Arrays.sort(nums);
int count = 1;
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1])
count++;
else {
if (count > upLimit)
result.add(nums[i - 1]);
count = 1;
}
}
return result;
}
}
My test result:
从上面那道题目得来的思路。直接排序，然后遍历，记录次数，如果过了，就放进List。
就这么简单。
排序用的是堆排序， in-place。所以不需要额外空间。
复杂度线性，空间复杂度常数的做法：
Paste_Image.png
http://www.programcreek.com/2014/07/leetcode-majority-element-ii-java/
**
总结: Array
赶紧睡了，明天要早起。今天，终于到60题啦。
还有就是，61B上完，应该来得及。
题目走之前，我至少要刷到80，最好到100.
别忘了工作简历！
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> majorityElement(int[] nums) {
ArrayList<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0)
return ret;
Integer c1 = null;
Integer c2 = null;
int counter1 = 0;
int counter2 = 0;
for (int i = 0; i < nums.length; i++) {
if (c1 != null && c1.intValue() == nums[i])
counter1++;
else if (c2 != null && c2.intValue() == nums[i])
counter2++;
else if (counter1 == 0) {
c1 = new Integer(nums[i]);
counter1++;
}
else if (counter2 == 0) {
c2 = new Integer(nums[i]);
counter2++;
}
else {
counter1--;
counter2--;
}
}
counter1 = 0;
counter2 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == c1.intValue()) {
counter1++;
}
else if (c2 != null && nums[i] == c2.intValue()) {
counter2++;
}
}
if (counter1 > nums.length / 3)
ret.add(c1.intValue());
if (counter2 > nums.length / 3)
ret.add(c2.intValue());
return ret;
}
}
自己看着提示重写了下两个人的投票算法。还可以。
注意点主要就是，最后还需要确认下，这两个candidate是不是Majority。
然后这种题目是有统一做法的。
假设要求出现 > 1 / n 次。
那么，设置 n - 1 个candidate
Integer c1, c2, .... c(n - 1)
int counter1, counter2, ... counter(n - 1)
然后代码和这上面的差不多。要是和所有的candidate都不同。就统一减去1.
如果和某个相同，就counter++
如果counter == 0, 就一个个的初始化。
差不多就这样了。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<Integer> majorityElement(int[] nums) {
List<Integer> ret = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return ret;
}
Integer i1 = null;
Integer i2 = null;
int c1 = 0;
int c2 = 0;
for (int i = 0; i < nums.length; i++) {
if (i1 != null && i1.intValue() == nums[i]) {
c1++;
}
else if (i2 != null && i2.intValue() == nums[i]) {
c2++;
}
else if (i1 == null) {
i1 = new Integer(nums[i]);
c1++;
}
else if (i2 == null) {
i2 = new Integer(nums[i]);
c2++;
}
else {
c1--;
c2--;
if (c1 == 0) {
i1 = null;
}
if (c2 == 0) {
i2 = null;
}
}
}
if (i1 != null) {
int target = i1.intValue();
int counter = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
counter++;
}
}
if (counter > nums.length / 3) {
ret.add(target);
}
}
if (i2 != null) {
int target = i2.intValue();
int counter = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
counter++;
}
}
if (counter > nums.length / 3) {
ret.add(target);
}
}
return ret;
}
}
和之前的做法差不多。
Anyway, Good luck, Richardo! -- 09/04/2016
