LeetCode229 MajorityElementII java题解

题目：Given an integer array of size n, find all elements that appear more than <code style="box-sizing: border-box; font-family: Menlo, Monaco, Consolas, 'Courier New', monospace; font-size: 12.6000003814697px; padding: 2px 4px; color: rgb(199, 37, 78); border-radius: 4px; line-height: 30px; background-color: rgb(249, 242, 244);"> n/3 </code> times. The algorithm should run in linear time and in O(1) space.求出现次数大于三分之一数组的长度，所以最多就只有2个这样的元素，，题目要求线性时间复杂度和常数的空间复杂度，所以这题就不能使用哈希表来进行求解了。通过第一次遍历找出出现次数最多的两个元素（利用此消彼长的原理），这时候不能得到具体出现多少次，所以得到两个出现次数最多的元素后，需要再遍历一次得到切确的出现次数看有没超过数组长度的三分之一代码：import java.util.ArrayList;import java.util.List;public class LeetCode229_MajorityElementII {/** * @param args */public static void main(String[] args) {// TODO Auto-generated method stubint[] nums={1,2,3,4,5,6,1,1,1,2,2,2,1,2};List<Integer> result=majorityElement(nums);for(int i=0;i<result.size();i++)System.out.println(result.get(i));}public static List<Integer> majorityElement(int[] nums) {List<Integer> result=new ArrayList<Integer>();int majorNum1=0,majorNum2=0,majorCount1=0,majorCount2=0;for(int i=0;i<nums.length;i++){if(majorCount1==0){majorNum1=nums[i];majorCount1=1;}else if(majorNum1==nums[i]){majorCount1++;}else if(majorCount2==0){majorNum2=nums[i];majorCount2=1;}else if(majorNum2==nums[i]){majorCount2++;}else {majorCount1–;majorCount2–;}}majorCount1=0;majorCount2=0;for(int i=0;i<nums.length;i++){if(nums[i]==majorNum1)majorCount1++;if(nums[i]==majorNum2)majorCount2++;}if(majorCount1>nums.length/3)result.add(majorNum1);if(majorCount2>nums.length/3&&majorNum2!=majorNum1)result.add(majorNum2);return result;}}

每一件事都要用多方面的角度来看它

相关文章：

你感兴趣的文章：

标签云：