This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Array related algorithm topic is relatively high frequency, through this article, I hope to be able to help your array related algorithm ability.

Find the largest and smallest elements in the given array

Problem Description:

I give you an array of numbers. You need to find the smallest and largest number in the array.

Ideas:

  • Define two variables, Max, min, to hold the largest and smallest elements
  • Through the array
    • If the current element is greater than Max, the current element is assigned to Max
    • If the current element is less than min, the current element is assigned to min
  • Finally, Max and min are the largest and smallest elements

Code implementation:

public class FindLargestSmallestNumberMain {

    public static void main(String[] args) {

        int arr[] = new int[] {12.56.76.89.100.343.21.234};
        // Assign the first element to
        int min = arr[0];
        int max = arr[0];

        for(int i=1; i< arr.length; i++)
        {
            if(arr[i] > max)
                max = arr[i];
            else if (arr[i] < min)
                min = arr[i];
        }
        System.out.println("Smallest Number is : " + min);
        System.out.println("max Number is : "+ max); }}Copy the code

Find the missing number in the array

Problem Description:

Given an array of incrementing integers from 1 to n, but one number from 1 to n is missing. You need to provide an optimal solution to find the missing numbers. Numbers are not repeated in the array.

Such as:

int[] arr1={7.5.6.1.4.2};
Missing number : 3
int[] arr2={5.3.1.2};
Missing number : 4
Copy the code

Ideas:

  • Because the elements in an array are incrementing, formulas can be usedn=n*(n+1)/2Take the sum of n numbers
  • Computes the sum of the elements in the given array
  • Subtract the sum of the elements of the array from the sum of n numbers and the result is the missing number

Code implementation:

public class MissingNumberMain {
 
    public static void main(String[] args) {
 
        int[] arr1={7.5.6.1.4.2};
        System.out.println("Missing number from array arr1: "+missingNumber(arr1));
        int[] arr2={5.3.1.2};
        System.out.println("Missing number from array arr2: "+missingNumber(arr2));
 
    }
 
    public static int missingNumber(int[] arr)
    {
        int n=arr.length+1;
        int sum=n*(n+1) /2;
        int restSum=0;
        for (int i = 0; i < arr.length; i++) {
            restSum+=arr[i];
        }
        int missingNumber=sum-restSum;
        returnmissingNumber; }}Copy the code

Finds elements from a rotated ordered array

Problem Description:

Given a sorted and rotated array, it looks like this:

int arr[]={16.19.21.25.3.5.8.10};
Copy the code

The array is obtained by rotating an ordered array arr[]={3,5,8,10,16,19,21,25}.

Requires a specified element to be searched in an array of order log n time complexity.

Ideas:

  • If the number group is traversed directly, the time complexity isO(n), does not meet the requirements of the topic;
  • Because arrays are rotated by ordered arrays, they are ordered before and after some index;
  • And then follow the dichotomy.

Algorithm logic:

  • Mid =(low+high)/2;
  • Returns if arr[mid] is equal to the number being looked for;
  • If [low…mid] is ordered;
    • Mid =mid; mid =mid;
    • Mid =mid+1; mid =mid+1;
  • If [mid…high] is ordered;
    • Mid =mid+1; mid =mid+1;
    • [mid…high] =mid-1;

Code implementation:

public class SearchElementSortedAndRotatedArrayMain {

    public static void main(String[] args) {
        int arr[] = {16.19.21.25.3.5.8.10};
        System.out.println("Index of element 5 : " + findElementRotatedSortedArray(arr, 0, arr.length - 1.5));
    }

    public static int findElementRotatedSortedArray(int[] arr, int low, int high, int number) {
        int mid;
        while (low <= high) {
            mid = low + ((high - low) / 2);

            if (arr[mid] == number) {
                return mid;
            }
            if (arr[mid] <= arr[high]) {
                // The right-hand side is ordered
                if (number > arr[mid] && number <= arr[high]) {
                    low = mid + 1;
                } else {
                    high = mid - 1; }}else {
                // The left part is ordered
                if (arr[low] <= number && number < arr[mid]) {
                    high = mid - 1;
                } else {
                    low = mid + 1; }}}return -1; }}Copy the code

Find the smallest element in the ordered rotation array

Problem Description:

An ordered rotation array is defined as before, for example:

int arr[]={16.19.21.25.3.5.8.10};
Copy the code

It also requires order log n time.

Ideas:

Similar to the above problem, since an array can be split into two ordered arrays, it can be done by a variation of the binary search method;

  • Mid =(low+high)/2;
  • If [mid…high] is ordered;
    • The minimum is on the right, high=mid;
  • Otherwise, the minimum is on the left, low= mid+1;

Code implementation:

public class MinimumElementSortedAndRotatedArrayMain {

    public static void main(String[] args) {
        int arr[] = {16.19.21.25.3.5.8.10};
        System.out.println("Minimum element in the array : " + findMinimumElementRotatedSortedArray(arr, 0, arr.length - 1));
    }
    public static int findMinimumElementRotatedSortedArray(int[] arr, int low, int high) {
        int mid;
        while (low < high) {
            mid = low + ((high - low) / 2);
            if (arr[mid] < arr[high]) {
                high = mid;
            } else {
                low = mid+1; }}returnarr[low]; }}Copy the code

Finds the second largest and element in the array

Problem Description:

Given a rotated ordered array, look like this:

int[] arr1={7.5.6.1.4.2};
Copy the code

Find the second largest element: 6

Ideas:

You can sort an array and return the next-to-last element of the array in order nlogn.

  • Define the highest and secondHighest value variables, secondHighest
  • Iterate over the array
  • If the current element is greater than the maximum
    • Assign highest to secondHighest
    • Assigns the current element to Highest
  • Otherwise, if the current element is greater than secondHighest
    • Assign the current element to secondHighest

Code implementation:

public class FindSecondLargestMain {
    public static void main(String args[]) {
        int[] arr1 = {7.5.6.1.4.2};
        int secondHighest = findSecondLargestNumberInTheArray(arr1);
        System.out.println("Second largest element in the array : " + secondHighest);
    }

    public static int findSecondLargestNumberInTheArray(int array[]) {
        int highest = Integer.MIN_VALUE;
        int secondHighest = Integer.MIN_VALUE;

        // go through the number group
        for (int i = 0; i < array.length; i++) {
            // If the current value is greater than the maximum value
            if (array[i] > highest) {
                // The maximum value is assigned to the second largest value
                secondHighest = highest;
                // The current value is assigned to the maximum value
                highest = array[i];
            } else if(array[i] > secondHighest && array[i] ! = highest)// Assign the current value to the second largest value
                secondHighest = array[i];
        }
        returnsecondHighest; }}Copy the code

Find the number of odd occurrences in the array

Title description:

Given an array of integers, only one number occurs an odd number of times and all the other numbers occur an even number of times. You need to find the odd number of occurrences. It takes O(n) time complexity and O(1) space complexity to solve it.

Idea 1:

Violent solution: A two-layer loop is used to record the number of occurrences of each element. The time complexity of this method is O(n^2), which is not optimal.

Idea 2:

If Hash is used, the number is used as the key and the number of occurrences is used as the value. If the key is repeated, value+1 is used. The time complexity of this solution is O(n), but the space complexity is also O(n), which does not meet requirements.

Code implementation:

int getOddTimesElementHashing(int ar[]) {
        int i;
        HashMap<Integer, Integer> elements = new HashMap<Integer, Integer>();
        for (i = 0; i < ar.length; i++) {
            int element = ar[i];
            if (elements.get(element) == null) {
                elements.put(element, 1);
            } else{
                elements.put(element, elements.get(element) + 1); }}for (Entry<Integer, Integer> entry : elements.entrySet()) {
            if (entry.getValue() % 2= =1) {
                returnentry.getKey(); }}return -1;
    }
Copy the code

Idea 3:

Bit-based xOR operations.

Xor operation: same is 0, different is 1. If a=1001,b=1010, then a^b=0010, a^a=0000.

According to the description, only one digit in the array has an odd number of occurrences, and all the other digits have an even number of occurrences. If all the digits are xor, the result is the odd number of occurrences.

Code implementation:

int getOddTimesElement(int arr[]) {
    int i;
    int result = 0;
    for (i = 0; i < arr.length; i++) {
        result = result ^ arr[i];
    }
    return result;
}
Copy the code

The time complexity of the solution is O(n). Because only one variable result is used, the space complexity is O(1).

Calculate the minimum number of platforms required for a railway station

Title description:

Given two arrays corresponding to the arrival time and departure time of vehicles at the railway station, calculate the minimum number of platforms required by the railway station.

// Arrive schedule
arrival[] = {1:00.1:40.1:50.2:00.2:15.4:00}
// Exit schedule
departure[] = {1:10.3:00.2:20.2:30.3:15.6:00}
// The minimum number of platforms required = 4
Copy the code

Idea 1:

Iterate over both arrays to check how much each arrival and outbound time interval overlaps.

The time complexity is O(n^2), which is not optimal.

Idea 2:

Use merge sort logic.

  • Sort the arriving and departing arrays;
  • Since the number of arrivals is the same as the number of outbound, the time is compared by taking the elements from both arrays at the same location;
  • If the arrival time is early, the number of platforms is increased by 1;
  • If the departure time is early, the number of platforms is reduced by 1;
  • Record the maximum number of platforms in this process;
  • Finally returns the value of the maximum number of platforms.

The time complexity of this algorithm is O(n*log n).

Code implementation:

public class TrainPlatformMain {
    public static void main(String args[]) {
        // arr[] = {1:00, 1:40, 1:50, 2:00, 2:15, 4:00}
        // dep[] = {1:10, 3:00, 2:20, 2:30, 3:15, 6:00}
        int arr[] = {100.140.150.200.215.400};
        int dep[] = {110.300.210.230.315.600};
        System.out.println("Minimum number of platforms required =" + findPlatformsRequiredForStation(arr, dep, arr.length));
    }

    static int findPlatformsRequiredForStation(int arr[], int dep[], int n) {
        int platform_needed = 0, maxPlatforms = 0;
        Arrays.sort(arr);
        Arrays.sort(dep);
        int i = 0, j = 0;
        // similar to merge sort
        while (i < n && j < n) {
            if (arr[i] < dep[j]) {
                platform_needed++;
                i++;
                if (platform_needed > maxPlatforms)
                    maxPlatforms = platform_needed;
            } else{ platform_needed--; j++; }}returnmaxPlatforms; }}Copy the code

The two numbers in an array whose sum is closest to zero

Title description:

In an array of positive and negative numbers, find the two numbers in the array whose sum comes closest to 0.

Such as:

array[]={1.3, -5.7.8.20, -40.6};
// The two numbers closest to 0 are: -5 and 6
Copy the code

Idea 1:

Violent solution: Sum all numbers in pairs, if the absolute value of the sum is smaller, then assign to record the value of both numbers.

The time complexity of this method is O(n^2), which is not optimal.

Code implementation:

public static void findPairWithMinSumBruteForce(int arr[]) {
    if (arr.length < 2)
        return;
    // Specify that the sum of the first two numbers is closest to 0
    int minimumSum = arr[0] + arr[1];
    int pair1stIndex = 0;
    int pair2ndIndex = 1;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int tempSum = arr[i] + arr[j];
            if (Math.abs(tempSum) < Math.abs(minimumSum)) {
                pair1stIndex = i;
                pair2ndIndex = j;
                minimumSum = tempSum;
            }
        }
    }
    System.out.println("And the two numbers closest to 0 are:" + arr[pair1stIndex] + "" + arr[pair2ndIndex]);
}
Copy the code

Idea 2:

  • Sort the array;
  • Define two indexes corresponding to the array starting position l=0, one at the end position r=n-1;
  • The conditional loop is l
  • Calculate the sum of arr[l]+arr[r]
  • If abs(sum)
  • If sum is greater than 0, then to get closer to 0, we need to move the large value smaller, r–;
  • If sum is less than 0, then to get closer to 0 we have to move the small value up, l++.

Code implementation:

public static void findPairWithMinSum(int arr[]) {
    Arrays.sort(arr);
    int sum = 0;
    int minimumSum = Integer.MAX_VALUE;
    int n = arr.length;
    // left and right index variables
    int l = 0, r = n - 1;

    int minLeft = l, minRight = n - 1;

    while (l < r) {
        sum = arr[l] + arr[r];
        // if abs(sum)
        if (Math.abs(sum) < Math.abs(minimumSum)) {
            minimumSum = sum;
            minLeft = l;
            minRight = r;
        }
        if (sum < 0)
            l++;
        else
            r--;
    }
    System.out.println("And the two numbers closest to 0 are:" + arr[minLeft] + "" + arr[minRight]);
}
Copy the code

The time complexity of this algorithm is O(NLogN).

The two numbers in an array whose sum is closest to X

This problem is an advanced version of the previous problem. Find the number where the sum of two numbers is closest to X.

Idea 1:

Violent solution: two-layer loop, sum is compared with the nearest number, if smaller, record the corresponding number, time complexity is O(n^2), not optimal solution.

Idea 2:

The difference with the previous problem is that the value to compare the summation results is the specified X, not 0, and the results of abs() function cannot be directly used for comparison. So how do you deal with that?

The solution to the should problem can be obtained by subtracting X from the abs() result.

  • Sort the array;
  • Define two indexes corresponding to the array starting position l=0, one at the end position r=n-1;
  • The conditional loop is l
  • To calculatearr[l]+arr[r]-xThe results of the diff
  • If abs(diff)
  • If sum is greater than x, then to get closer to x we need to move the large value smaller, r–;
  • If sum is less than x, then to get closer to x we have to move the small value up, l++.

Code implementation:

public static void findPairWithClosestToX(int arr[], int X) {
    Arrays.sort(arr);
    int minimumDiff = Integer.MAX_VALUE;
    int n = arr.length;

    int l = 0, r = n - 1;

    int minLeft = l, minRight = n - 1;
    while (l < r) {
        int currentDiff = Math.abs(arr[l] + arr[r] - X);
        // If abs(diff)
        if (currentDiff < minimumDiff) {
            minimumDiff = currentDiff;
            minLeft = l;
            minRight = r;
        }
        if (arr[l] + arr[r] < X)
            l++;
        else
            r--;
    }
    System.out.println("And the two numbers closest to X are:" + arr[minLeft] + "" + arr[minRight]);
}
Copy the code

The sum of two numbers in an array is equal to all combinations of X

Title description:

Given an array and a specified number, find the sum of all two numbers in the array equal to the specified number.

Idea 1:

The two-layer cyclic violent solution has low time complexity and is not optimal.

Code implementation:

public static void findPairsWithSumEqualsToXBruteForce(int arr[], int X) {
    if (arr.length < 2)
        return;
    System.out.println("Brute force solve a combination of two numbers equal to X:");
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            int tempSum = arr[i] + arr[j];

            if (tempSum == X) {
                System.out.println(arr[i] + ""+ arr[j]); }}}}Copy the code

Idea 2:

Sort the array;

Traverse both ends of the array until they meet, using L for left and R for right;

If arr[l]+arr[r]=X, then the condition is met, print the result, l–,r–;

If arr[L]+ ARr [r]>X, it indicates that the result is too large, and the large value needs to be reduced, r–;

If arr[l]+arr[r]<X, it indicates that the result is small, and the small value needs to be increased, L ++;

Code implementation:

public static void findPairsEqualsToX(int arr[], int X) {
    int n = arr.length;
    if (n < 2)
        return;
    Arrays.sort(arr);
    System.out.println("A combination of two numbers equal to X:");

    int l = 0, r = n - 1;

    while (l < r) {
        int currentSum = arr[l] + arr[r];
        if (currentSum == X) {
            System.out.println(arr[l] + "" + arr[r]);
            l++;
            r--;
        } else if (arr[l] + arr[r] < X)
            l++;
        elser--; }}Copy the code

The time complexity of the solution is O(NLogN).

Idea 3:

  • Using HashMap, place the value of an array element as a key and the subscript as a value into the map.
  • Traversal number group;
  • If x-arr [I] exists in the HashMap, the result is fetched from the Map, indicating that the condition is met.

Code implementation:

public static void findPairsEqualsToXUsingHashing(int arr[], int X) {
    HashMap<Integer, Integer> elementIndexMap = new HashMap<>();
    System.out.println("A combination of two numbers equal to X:");
    for (int i = 0; i < arr.length; i++) {
        elementIndexMap.put(arr[i], i);
    }
    for (int i = 0; i < arr.length; i++) {
        if(elementIndexMap.get(X - arr[i]) ! =null&& elementIndexMap.get(X - arr[i]) ! = i)//
        {
            System.out.println(arr[i] + ""+ (X - arr[i])); }}}Copy the code