首页 > 代码库 > 求数组主元素的递归算法
求数组主元素的递归算法
数组A是具有n个元素的数组,x是A中的一个元素,若A中有一半以上的元素与A相同,则称x是数组A的主元素。例如 ,数组A={1,3,2,3,3,4,3},元素3就是该数组的主元素。
1、移去数组中的两个不同元素后,如果原来数组中有主元素,那么该主元素依然是新数组的主元素。
2、如果数组2k个元素中有k个元素相同(k<n/2),移去这2k个元素以后,如果原来数组中有主元素,那么该主元素依然是新数组的主元素。
如果新数组只剩下一个元素,该元素可作为主元素的候选者。新数组是若干个相同元素,该元素可作为主元素的候选者。没有剩下元素时,则原来数组没有主元素。
count为一个初值为0的计数器,当扫描元素时,如果当前元素和num表示的元素相等,则计数器加1,否则计数器减1.当所有元素扫面以后,如果计数器大于0,说明数组还有若干个与num相等的元素未移除,则num为主元素候选者。
1 public class Demo<T> { 2 3 public T num; 4 public T A[]; 5 6 public Demo(T A[]) { 7 this.A = A; 8 } 9 10 public boolean candidate(int m) { 11 int count = 1; 12 int i = m; 13 int n = A.length; 14 num = A[i]; 15 while (i < n - 1 && count > 0) { 16 if (A[++i].equals(num)) 17 count++; 18 else 19 count--; 20 } 21 if (i == n - 1 && count > 0) 22 return true; 23 else if (i == n - 1 && count == 0) { 24 return false; 25 } else 26 return candidate(i + 1); 27 } 28 29 public boolean majority() { 30 int count = 0; 31 boolean flag = candidate(0); 32 33 if (flag) { 34 for (T a : A) { 35 if (num.equals(a)) 36 count++; 37 } 38 if (count < A.length / 2) 39 return false; 40 } 41 return flag; 42 } 43 44 public T getNum() { 45 return num; 46 } 47 48 public static void main(String[] args) { 49 50 String A[] = {"a", "c", "a", "b", "a" }; 51 Demo<String> d1 = new Demo<>(A); 52 boolean sign = d1.majority(); 53 if (sign) { 54 System.out.println(d1.getNum()); 55 } else 56 System.out.println("主元素不存在"); 57 } 58 }
求数组主元素的递归算法
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。