首页 > 代码库 > 每日一记--2014.9.15
每日一记--2014.9.15
今天的程序还有待改进，写的可能比较冗长了，虽然逻辑不难，自己也是debug了一会儿。
问题是：找数值中的主元素，即个数超过半数的元素。
首先找出唯一的一个候选元素，然后再遍历数值统计其个数，看是否大于数组长度的二分之一，如大于则返回此主元素，若小于则表明没有主元素那么返回-1（假设数组中的数均为正整数）。
如何寻找唯一的候选元素：
1.利用递归
2.为找出A中的候选元，先构造B。逐次比较A中的两个元素:比较A1和A2，若相等，则放入B；否则什么也不做。然后比较A3和A4,若相等，则放入B；否则什么也不做。依次方式继续直到读完整个A（当A中有奇数个元素时，则将最后一个元素直接放入B中）然后寻找B中的候选元素。一直递归下去，直到B中只剩一个候选元素为止，或者B中元素为0个，则证明没有主元素。
1 package mainElement; 2 3 public class MainElement { 4 5 public static void main(String[] args) { 6 // TODO Auto-generated method stub 7 int[] aa = new int[] {5,2,3,5,5,5,1,7,5,9,5}; 8 System.out.println(findMain(aa,aa.length)); 9 }10 11 private static int findMain(int[] aa, int length) {12 int mainEle = findMainCandi(aa,length);13 if(mainEle!=-1){14 int count=0;15 for(int i=0;i<length;i++){16 if(aa[i]==mainEle)17 count++;18 }19 if(count>(length/2)){20 return mainEle;21 }else{22 return -1;23 }24 25 }else{26 return -1;27 }28 29 }30 31 // 如果有候选主元素就返回此候选，如没有返回-132 33 private static int findMainCandi(int[] aa,int len) {34 // TODO Auto-generated method stub35 if (len == 1) {36 return aa[0];37 } else {38 int length =0;39 int[] bb = new int[len];40 if (len % 2 == 0) {41 int j=0;42 for (int i = 0; i < len; i = i + 2) {43 if (aa[i] == aa[i + 1])44 bb[j++] = aa[i];45 }46 if(j==0)47 return -1;48 else49 length=j;50 } else {51 int j=0;52 for (int i = 0; i < len - 1; i = i + 2) {53 if (aa[i] == aa[i + 1])54 bb[j++] = aa[i];55 }56 bb[j] = aa[len - 1];57 length=j+1;58 }59 return findMain(bb,length);60 }61 }62 }
每日一记--2014.9.15
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。