基础算法之一----主要元素

Question

主要元素是指大小为N的数组中重复出现次数超过N/2的元素；
如
2,3,3,2,3的主要元素是3
2,1,3,3无主要元素问题：给定数组，快速得到其主要元素

Answer 1

遍历一遍 hashmap存出现次数 取最大次数的就可以了

Answer 2

据说有个算法，很有趣，我简单说一下思路
1 拿到一个数
2 如果这个数和上一个数相同，则次数+1，
  如果和上一个数不同，则次数减1，
      如果次数为0，则这个数作为第一个数，次数为1
3 转到1，继续最后剩下的数就是你要的数。这个算法的一个前提，就是一定有一个数超过了1/2， 否则最后的结果可能是错误的。如果使用常规算法，可以用Map来实现，里面保存着当前数字出现的次数，

Answer 3

public static void main(String[] args){
 char test[] ={'2','3','3','2','3','2','2'};
 int array[] = new int[256];
 for(int i =0;i<test.length;i++){
 int index = (int) test[i];
    array[index] ++;
 }
 for(int r = 0;r<256;r++){
 if(array[r]>(test.length/2)){
 char result = (char)r;
 System.out.println(result);
 }
 }
 }
给分啦...写了几分钟哟...

Answer 4

/**
 * 编程之美-寻找发帖"水王"。<br>
 * 每个帖子均有回复，总发帖量超过一半了。找出这个人的ID.
 * 
 * @author 赵学庆，Java世纪网(java2000.net)
 * 
 */
public class T {  /**
   * 查找ID.
   * 
   * @param id
   *          所有帖子的作者ID
   * @return
   */
  public static int find(int[] id) {
    int rtn = Integer.MIN_VALUE;
    int nTimes, i;
    for (i = nTimes = 0; i < id.length; i++) {
      if (nTimes == 0) {
        rtn = id[i];
        nTimes = 1;
      } else {
        if (rtn == id[i]) {
          nTimes++;
        } else {
          nTimes--;
        }
      }
    }
    return rtn;
  }  public static void main(String[] args) {
    int[] id = { 2, 3, 4, 5, 1, 2, 1, 3, 5, 7, 31, 3, 2, 2, 1, 12, 4, 56, 23, 12, 4, 1, 3, 4,
        2, 2, 1, 3, 1, 23, 1, 5, 3, 1, 3, 12, 1, 2, 1, 1, 1, 2, 2, 2 };
    System.out.println(find(id));
  }
}
紫竹大人的代码..不过不理解为什么这样取出来的是最大的数呢?...

Answer 5

public static void main(String[] args){ 
int test[] ={2,3,3,2,3,2,2}; 
Map map = new HashMap();
for(int i =0;i <test.length;i++){ 
  String key = String.valueOf(test[i]); 
  if(map.containsKey(key))
  {
  String value = map.get(key).toString();
  if(value != null)
  {
  value = String.valueOf((Integer.parseInt(value) + 1));
  }
  else
  {
  value = "0";
  }
  }   
} 
} 
这个时候map中的key就是数据的值，value就是数据的个数了，，，把值拿出来和数组的2分1比较一下就出来了。

Answer 6

package commontest;public class MainElement {
private int findMain(int[] arr){
int j = 0;
for(int i=0;i<arr.length;++i){
try{
if(arr[i]==arr[++i]){
arr[j] = arr[i];
j++;
}
}catch(Exception e){
int temp = arr[--i];
if(j==0){
for(int b=0;b<arr.length-1;++b){
if(arr[b]==temp){
arr[j]=temp;
j++;
break;
}
}
}else{
for(int b=0;b<j;++b){
if(arr[b]==temp){
arr[j]=temp;
j++;
break;
}
}
}
}
}
if(j==1){
return arr[0];
}
if(j==0){
throw new RuntimeException("Cannot find!");
}
int[] temp = new int[j];
System.arraycopy(arr, 0, temp, 0, j);
return findMain(temp);
}

public static void main(String[] args){
int[] a = new int[]{2,1,2,1,4,2,1};
int result = new MainElement().findMain(a);
System.out.println(result);
}
}貌似可以~~