"Sprint to Dachang foundation 2"

Sprint Dachang Foundation

1. Given an ordered array , find （>=value） The leftmost position of

Ideas ： Use dichotomy , Use one index Variable , Record every time (>=value) The location of , Finally back to .

public class Code05_BSNearLeft {
    
    public static int nearestIndex(int[] arr, int value){
    
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while(L <= R){
    
            int mid = L + ((R - L) >> 1);
            if(arr[mid] >= value){
    
                index = mid;
                R = mid - 1;
            }else{
    
                L = mid + 1;
            }
        }
        return index;
    }
}

2. Given an ordered array , find （<=value） Right most position of

Ideas ： Use dichotomy , Use one index Variable , Record every time (<=value) The location of , Finally back to .

public class Code06_BSNearRight {
    
    public static int nearestRight(int[] arr, int value){
    
        int L = 0;
        int R = arr.length - 1;
        int index = -1;
        while(L <= R){
    
            int mid = L +((R - L) >> 1);
            if(arr[mid]<= value){
    
                index = mid;
                L = mid + 1;
            }else{
    
                R = mid - 1;
            }
        }
        return index;
    }
}

3. Given an array , Only one of them appears odd number of times , All the other numbers appear an even number of times . Print the number of odd occurrences .

Ideas ： The container method can be used to record the number of occurrences of each number , This is not the optimal solution .

Optimal solution ： Adopt XOR method ,（0^N = N）（N ^ N = 0）, And XOR operation satisfies commutative law and distributive law

public static void printOddTimesNum1(int[] arr){
    
        int eor = 0;
        for (int num : arr) {
    
            eor ^= num;
        }
        System.out.println(eor);
    }

4. Find the rightmost... In the specified number binary 1

Ideas ： Whether positive or negative , perform N&(-N) Can be taken out N The most the right side 1, Also equivalent to N&(~N + 1).

public static int bit1Right(int N){
    
	return N & (-N);
	//return N & (~N + 1);
}

5. Given an array , Only two different numbers appear odd times , The remaining numbers appear an even number of times

Ideas ： The container method can be used to record the number of occurrences of each number , This is not the optimal solution .

Optimal solution ： First, XOR each number in the array , The result is the result of the two odd numbers of exclusive or （eor）, Take the rightmost... In the binary of the result 1（onlyOne）. Compare the numbers in the array with onlyOne Conduct & operation ,( Elements in an array )&(onlyOne) It's not equal to 0 To perform exclusive or operation on the number of .onlyOne Finally, it is one of the two numbers that appear odd times , then （eor）^（onlyOne） Get another number that occurs an odd number of times .

public static void printOddTimesNum2(int[] arr){
    
        int eor = 0;
        for (int num : arr) {
    
            eor ^= num;
        }
        int rightOne = eor & (-eor);
        int onlyOne = 0;
        for (int num : arr) {
    
            if((num & rightOne) != 0){
    
                onlyOne ^= num;
            }
        }
        System.out.println(onlyOne + " " + (eor ^ onlyOne));
    }