Arrange the array into the smallest number_ Reverse pairs in an array (merge Statistics)_ Number of occurrences of a number in an ascending array_ Ugly number (Sword finger offer)

Sort

Make the array the smallest number

Topic link

import java.util.*;
public class Solution {
    
    public String PrintMinNumber(int [] numbers) {
    
        // Empty array 
        if(numbers == null || numbers.length == 0)
            return "";
        String[] nums = new String[numbers.length];
        // Convert numbers to characters 
        for(int i = 0; i < numbers.length; i++)
            nums[i] = numbers[i]+"";
        // Sort by overload 
        Arrays.sort(nums, new Comparator<String>() {
    
            public int compare(String s1, String s2) {
    
                return (s1 + s2).compareTo(s2 + s1);
            }
        });
        StringBuilder res = new StringBuilder();
        // String overlay 
        for(int i = 0; i < nums.length; i++)
            res.append(nums[i]);
        return res.toString();
    }
}

• The key point of this topic is to design a sort by yourself , adopt Comparator Interface !
• String splicing s1 + s21>s2 + s1 explain s1 and s2 Positions need to be exchanged !

Similar topics : Median in data stream

Understand the meaning of the question !

import java.util.*;
public class Solution {
    
    // Save the data flow table in !
    private ArrayList<Integer> table = new ArrayList<>();
    public void Insert(Integer num) {
    
        // stay table Insert... Into the data stream num value !
        if(table.isEmpty()){
    
            // Direct tail insertion 
            table.add(num);
        }else{
    
            // Not empty , Find the right place to insert ! Ascending sort !
            int i = 0;
            for(i = 0;i< table.size();i++){
    
                if(table.get(i)>num){
    
                    // Found the right place !
                    table.add(i,num);
                    break;
                }
            }
            if(i==table.size()){
    
                // Tail insertion !
                table.add(i,num);
            }
        }
    }

    public Double GetMedian() {
    
        // Calculate the median !
        if(table.isEmpty()){
    
            return 0.0;
        }else{
    
            int size = table.size();
            if(size%2==0){
    
                // even numbers !
                return (double)(table.get(size/2)+table.get(size/2-1))/2;
            }else{
    
                // Odd number 
                return (double)table.get(size/2);
            }
        }
    }

}

• Insert considering the boundary problem !

Reverse pairs in arrays ( Merge Statistics )

Topic link

public class Solution {
    
    private int sum = 0;// Save the result value !
    public int InversePairs(int [] array) {
    
        // Merge Statistics !
        // Using the idea of merge sort , After all, count the number of groups of reverse order pairs when merging !
        if(array.length<2){
    
            // No reverse order team 
            return 0;
        }
        // Merge Statistics !
       mergeSort(array,0,array.length-1);
        return sum; 
    }
    public void mergeSort(int[] array,int left,int right){
    
        // Go ahead and divide !
        int mid = left + (right-left)/2;
       if(left<right){
    
           // Left interval !
           mergeSort(array,left,mid);
           // The right range !
           mergeSort(array,mid+1,right);
           // After and after 
           merge(array,left,mid,right);
       }
    }
    public void merge(int[] array,int left,int mid,int right){
    
        // When we merge, we need a temporary array to save 
        int[] tmp = new int[right-left+1];
        // Record the starting subscript position of the temporary array !
        int tmpIndex = 0;
        // Record the starting subscript position of the original array ( The temporary array data needs to be put into the original array )
        int arrayIndex = left;
        // Start position of left section !
        int l = left;
        // Start position of right section !
        int r = mid+1;
         // Compare and merge !
        while(l<=mid&&r<=right){
    
           if(array[l]<=array[r]){
    
               // No reverse order , Direct will l Subscripts are stored in temporary arrays !
               tmp[tmpIndex++] = array[l++];
           }else{
    
               // The reverse , In exchange for ( will r Save the subscript position )
               tmp[tmpIndex++] = array[r++];
               // Record the inverse logarithm !
               // When merging , The left and right arrays have been ordered separately !
               //l Greater than r Subscript element , That is to say l To mid The intervals are greater than r Subscript element 
               // So the inverse logarithm is  l Subscript position to  r Number of positions !
               sum += mid - l +1;
               sum %= 1000000007;
           }
            
        }
        // The interval lengths are not equal , There are residual values !
        while(l<=mid){
    
            tmp[tmpIndex++] = array[l++];
        }
        while(r<=right){
    
            tmp[tmpIndex++] = array[r++];
        }
        // Put the elements back into the original array !
        for(int x : tmp){
    
            array[arrayIndex++] = x;
        }
    }
}
 

The number of times a number appears in an ascending array

Topic link

public class Solution {
    
    public int GetNumberOfK(int [] array , int k) {
    
       // Array in order !
        // Two points search !
        int l = 0,r = array.length-1; 
        int mid = l + (r-l)/2;
        boolean flg = false;
        while(l<=r){
    
            mid = l + (r-l)/2;
            if(array[mid]>k){
    
                // Locate in the left section !
                r = mid-1;
            }else if(array[mid]<k){
    
                // Located in the right section !
                l = mid+1;
            }else{
    
                // equal !
                // find !
                flg = true;
                break;
            }
        }
        if(flg){
    
            for(int i = l;i<=mid;i++){
    
                if(array[i]==k){
    
                    // Left boundary of equal interval !
                    l = i;
                    break;
                }
            }
            for(int i = r;i>=mid;i--){
    
                if(array[i]==k){
    
                    // Right boundary of equal interval !
                    r = i;
                    break;
                }
            }
            return r - l +1;
        }
        return 0;
    }
}

public class Solution {
    
    public int GetNumberOfK(int [] array , int k) {
    
        // Find the boundary directly ,[left,right)  Left closed right away !
       return bisearch(array,k+0.5) - bisearch(array,k-0.5);
    }
    
    public int bisearch(int[] array,double k){
    
        int left = 0,right = array.length-1;
        while(left<=right){
    
            int mid = left + (right-left)/2;
            if(array[mid]<k){
    
                left = mid + 1;
                }else{
    
               right = mid - 1; 
            }
        }
        // If the binary here is not found, it returns a subscript greater than the value 
        return left;
    }
}

Ugly number

link

Their thinking ：

Let's look at the topic first , To include only qualitative factors 2、3 and 5 The number of is called ugly （Ugly Number）. for example 6、8 All ugly numbers , but 14 No , Because it contains quality factors 7. It's customary for us to 1 As the first ugly number .

With the above definition, we can know , The form of ugly number is 2^x3y5^z
So we can define an array res, Store the n Ugly number .
Because we have to sort the ugly numbers from small to large , So we have to put the corresponding ugly number in the corresponding subscript position , Put the small one in front .
Because the smallest ugly number is 1, So we initialize res[0]=1, So what's the next ugly number ？ We know for ourselves that 2.
But can we have a format , Who will get the next ugly number ？
At this time, the format of the ugly number we came up with above works , The form of ugly numbers is nothing more than this 2x3y5z
So we're going to res[n] To multiply 2、3、5, Then compare the smallest one , It's our next ugly number .

public class Solution {
    
    public int GetUglyNumber_Solution(int index) {
    
        if(index==0){
    
            return 0;
        }
        // utilize   Ugly number : 2^x*3^y*5^z!
        int[] arr = new int[index];// Before saving index Ugly value !
        arr[0] = 1;
        int i2 = 0,i3 = 0,i5 = 0;// Record 2/3/5 The number of times they are multiplied !
        for(int i = 1;i<index;i++){
    
            // take 3 The most clowns in the list are put in front !
            // Each time, the least ugly number is found !
            arr[i] = Math.min(arr[i2]*2,Math.min(arr[i3]*3,arr[i5]*5));
            if(arr[i]==arr[i2]*2){
    
                // Explain... Here  2  Multiply times plus one !
                i2++;
            }
            if(arr[i]==arr[i3]*3){
    
                // Explain... Here  3  Multiply times plus one !
                i3++;
            }
            if(arr[i]==arr[i5]*5){
    
                // Explain... Here  5  Multiply times plus one !
                i5++;
            }
        }
        return arr[index-1];
    }
}