One. Find the mode
Ideas:
- Sort (call the sorting algorithm in the system, high efficiency, write their own words can use merge)
- If a number is mode, then it will occupy the main body after sorting, so using index to locate the middle has a high probability of finding it, assuming that the number is a
- Scan left and right to find the bottom of the left and right boundary of the number, which is where the left and right of the pile of A go to, and calculate the number of the number, and initialize it as Mode, later find more times to cover it
- Divide and conquer, calculate the length of the array on both left sides of A (excluding A). If the length is less than the multiplications of A, it can be determined that there must be no mode in the array. If the length is larger than A, recurse step 3
import java.util.Arrays;
/ * * *@author SJ
* @date2020/10/10 * /
public class FindMode {
public static void main(String[] args) {
int[] nums={1.2.2.3.3.4.4.4.4.3.3.3};
findMode(nums);
}
public static void findMode(int[] nums){
Arrays.sort(nums);
Mode mode=fun(nums,0,nums.length-1);
System.out.println("The mode is:"+mode.value+"The multiplicity is:"+mode.num);
}
public static Mode fun(int[] nums,int left,int right){
int index=(right+left)/2;
int leftbound=findLeftIndex(nums,index,0);
int rigntbound=findRightIndex(nums,index,right);
int middleNums=rigntbound-leftbound+1;
Mode currentMode = new Mode(nums[index], middleNums);
if ((leftbound-left)>middleNums&&left<leftbound){
int temp=fun(nums,left,leftbound-1).num;
if (temp>middleNums){
currentMode.num=temp;
currentMode.value=fun(nums,left,leftbound-1).value; }}if ((right-rigntbound)>currentMode.num&&rigntbound<right){
int temp;
temp = fun(nums,rigntbound+1,right).num;
if (temp>middleNums){
currentMode.num=temp;
currentMode.value=fun(nums,rigntbound+1,right).value;}
}
return currentMode;
}
public static int findLeftIndex(int[] nums,int index,int left){
int leftBound=index;
for (int i = index-1; i >=left; i--) {
if(nums[i]==nums[index])
leftBound=i;
else
break;
}
return leftBound;
}
public static int findRightIndex(int[] nums,int index,int right){
int rightBound=index;
for (int i = index+1; i <=right; i++) {
if(nums[i]==nums[index])
rightBound=i;
else
break;
}
return rightBound;
}
public static class Mode{
public int value;
public int num=0;
public Mode(int value, int num) {
this.value = value;
this.num = num; }}}Copy the code"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe"... Mode: 3 Multiple: 5 Process finished with exit code 0Copy the codeTwo. Reverse order
import java.util.Arrays;
/ * * *@author SJ
* @date2020/10/10 * /
public class ReversePairs {
public static void main(String[] args) {
int[] nums={7.5.6.4};
int num=mergeSort(nums,0,nums.length-1);
// The answer is 5
System.out.println(num);
}
public static Integer[] temp=new Integer[10];
public static int merge(int[] nums,int left,int right){
int count=0;
for (int i = left; i <=right ; i++) {
temp[i]=nums[i];
}
int middle=(left+right)/2;
int l=left;
int r=middle+1;
for (int i = left; i<=right ; i++) {
if (l==middle+1&&r<right+1)
nums[i]=temp[r++];
else if (r==right+1&&l<middle+1)
nums[i]=temp[l++];
else if (temp[l]<=temp[r])
nums[i]=temp[l++];
else {
nums[i]=temp[r++];
// The right side of the array, r refers to the number on the right side. Logically, all the numbers in the left array are smaller than that, but only the numbers before L are smaller
// All numbers from L to middle are greater than him. So the numbers from L to middle are reversed with the current r
count+=middle-l+1; }}return count;
}
public static int mergeSort(int[] nums,int left,int right){
int leftCount=0;
int rightCount=0;
int aa=0;
if (left==right)
return 0;
else if (left<right){
leftCount= mergeSort(nums,left,(left+right)/2);
rightCount=mergeSort(nums,(left+right)/2+1,right);
aa= merge(nums,left,right);
}
returnleftCount+rightCount+aa; }}Copy the code"C: \ Program Files \ Java \ jdk1.8.0 _131 \ bin \ Java exe"
5
Process finished with exit code 0
Copy the codeIt was originally calculated using the static variable count, but wa was lost because the next set of test cases would still accumulate on the previous set of count. It was amended and passed.
Three. Not boring sequence
First, if this sequence (containing n integers) is a non-boring sequence list, then it must contain a number list[k] that occurs only once in the sequence.
List [0]~list[k-1] to list[k+1]~list[n-1] is not boring.
Bottom -> window decreases to 2 and the two numbers are different.
First of all, how do you find this number that only appears once? Look for violence?
Violent method: Use map to record the number of occurrences of each number, find the one that occurs only once, use it as the middle value, and start recursive repetition
import java.util.*;
/ * * *@author SJ
* @date2020/10/12 * /
public class SimpleNoBoring {
public static void main(String[] args) {
int[] nums = {1.2.3.2.1.2.2};
if (isNoBoring(nums, 0, nums.length - 1))
System.out.println("NoBoring!");
else
System.out.println("Boring!");
}
static class Num {
public int nums = 0;// The number of occurrences
public List<Integer> index;// A list of subscripts for the same data
public Num(int nums, int i) {
this.nums = nums;
index = newArrayList<>(); index.add(i); }}// All judgments are boring
public static boolean isNoBoring(int[] nums, int left, int right) {
// It is not boring to divide to only one
if (left==right)
return true;
// If there are only two numbers, as long as the two numbers are different, it is not boring
if (right - left == 1 ) {
if (nums[left]==nums[right])
return false;
}
// Divide more than three cases
else {
int middle = findGreatestIndex(nums,left,right);
if (middle==-1)// A unique number cannot be found
return false;
if (middle == left)// The only number that exists is on the far left
return isNoBoring(nums, middle + 1, right);
else if (middle == right)// The only number that exists is at the far right
return isNoBoring(nums, left, middle - 1);
else {// The only existing number is in the middle, then continue to divide
return isNoBoring(nums, 0, middle - 1) && isNoBoring(nums, middle + 1, right); }}return true;
}
// find unique data, return index if found, return -1 if not
public static int findGreatestIndex(int[] nums,int left,int right) {
//key is a numeric value
Map<Integer, Num> map = new HashMap<>();
for (int i = left; i <= right; i++) {
if (map.containsKey(nums[i])) {
Num num = map.get(nums[i]);
num.nums++;
num.index.add(i);
} else
map.put(nums[i], new Num(1, i));
}
Set<Integer> set = map.keySet();
for (Integer integer : set) {
if (map.get(integer).nums == 1) {
return map.get(integer).index.get(0); }}return -1; }}Copy the codeIn fact, after thinking about it, the above program has already recorded all the information of the array (including the number, the number of occurrences, the value is all the subscripts of the number) in the first scan, there is no need to new a map for each recursion to record. Each time we recurse, we just look for information from the map of the first new.
Give it a try.
.
The attempt failed.
// The list holds all the individual numbers. // Check if there is a number x in the list such that left<=x<=rightCopy the codeAfter the recursive split, as long as it is unique in the left~right range, it is not necessarily unique in the global scope, and the list records the index of the globally unique number, so I was wrong.