Java finds most elements in an array

Suunsr 2022-05-22 12:25:53 阅读数:731

javafindselementsarray

Catalog

I. sorting

2. Voting law

III. divide and conquer


  Most elements
  Given a size of n Array of , Find most of them .  Most elements refer to the number of occurrences in an array Greater than ⌊ n/2 ⌋ The elements of .  You can assume that the array is not empty , And there are always many elements in a given array .
We can solve this problem in many ways , Here are three ways

Most elements are modes , Understanding this truth makes it easy to solve this problem .

I. sorting

import java.util.Arrays;
public class Test {
public static void main(String[] args) {
int[] arr = {2,2,2,1,1,1,2};
System.out.println(manyNums(arr));
}
private static int manyNums(int[] arr) {
Arrays.sort(arr);// Use Arrays This class to sort
return arr[arr.length/2];// The middle number after sorting is the mode
}
}

2. Voting law

We can take things in real life as an example , For example, a class has 60 people , Now I want to choose a monitor , Yes A and B Two students ran for election , Those who voted for +1, Those who voted against -1, If he gets 31 ticket , Then add the positive and negative, and then more than half , Then he was elected .

public class Exercise1124 {
public static void main(String[] args) {
int[] nums = {7,7,5,7,5,1,5,7,5,5,7,7,7,7,7,7};
int num = manyNumVote(nums);
System.out.println(num);
}
private static int manyNumVote(int[] nums) {
// Record the number of people in favor
int count = 0;
Integer candidate = null;
for (int i:nums) {
//count= 0 You have to change candidates
if(count == 0){
candidate = i;
}
// disapproval
if(i != candidate){
count+=-1;
}else {
count+=1;
}
}
return candidate;
}
}

III. divide and conquer

Split an array into two parts , Mode exists in at least one of the subintervals .

The original question : Find the mode in an interval ,

Sub problem : Find the left mode in the left half leftNum, Find the right mode in the right half rightNum.

public class Exercise1124 {
public static void main(String[] args) {
int[] nums = {7, 7, 5, 7, 5, 1 ,5, 7 ,5, 5, 7, 7 ,7, 7, 7, 7};
int num = manyNumRecursion(nums);
System.out.println(num);
}
private static int manyNumRecursion(int[] nums) {
return manyNumRecursionInternal(nums,0,nums.length-1);
}
private static int manyNumRecursionInternal(int[] nums, int left, int right) {
if(left ==right){
// The interval has only one element
return nums[left];
}
int mid = (left + right)/2;
// Left half interval mode
int leftNum = manyNumRecursionInternal(nums,left,mid);
// And half interval mode
int rightNum = manyNumRecursionInternal(nums,mid+1,right);
if(leftNum == rightNum){
return leftNum;
}
// Need to know leftNum and rightNum The number of occurrences in the interval , Go back to the bigger one
int leftCount = numCount(nums,leftNum);
int rightCount = numCount(nums,rightNum);
return leftCount > rightCount ? leftNum : rightNum;
}
private static int numCount(int[] nums, int value) {
int count = 0;
for (int i:nums) {
if(i == value){
count++;
}
}
return count;
}
}

copyright:author[Suunsr],Please bring the original link to reprint, thank you. https://en.javamana.com/2022/142/202205211828001821.html