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

I am xiao Hei, a programmer in the Internet “casual”.

Water does not compete, you are in the flow

The content of this issue is an extension of the detailed analysis of Array algorithm problems in the last issue [Algorithm series]. It mainly includes the solution ideas and code implementation of three Array related algorithm problems.

Separate the odd and even numbers in the array

Title description:

Given an array of integers, separate the odd and even numbers in the array. The order of elements can be changed.

Ideas:

  • Suppose the array is arR []
  • Initialize two index variables, left=0,right=arr. Length -1
  • The incrementing left variable knows that the value is odd
  • Decrementing the right variable until the value is even
  • If left
  • You end up with even on the left and odd on the right

Code implementation:

package com.heiz.algorithm.array;

/ * * *@authorHei says Java *@ClassName SeparateOddEvenMain
 * @Description
 * @date2021/11/21 * * /
public class SeparateOddEvenMain {

    public static void main(String[] args) {

        int[] arr = {12.17.70.15.22.65.21.90};
        System.out.println("Original array:");
        for (int j : arr) {
            System.out.print(j + "");
        }
        separateEvenOddNumbers(arr);
        System.out.println("\n Array after odd and even separated:");
        for (int j : arr) {
            System.out.print(j + ""); }}public static void separateEvenOddNumbers(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        for (int i = 0; i < arr.length; i++) {

            while (arr[left] % 2= =0) {
                left++;
            }
            while (arr[right] % 2= =1) {
                right--;
            }

            if (left < right) {
                inttemp = arr[left]; arr[left] = arr[right]; arr[right] = temp; }}}}Copy the code

Running results:

Sort an array of 012 in O(n) time

Title description:

For example, int[] arr = [1, 2, 2, 0, 0,1,2,2,1].

Ideas:

Because there is only 012 in the array, we first iterate through the array, counting the occurrences of 0,1, and 2. Then we iterate through the array, reassigning the elements of the array to the occurrences of 012.

Steps:

  • Iterate over the given array once, incrementing the count of the numbers encountered.

  • Iterate through the array again, starting at index 0 and changing the values of the elements on the current index, running out of zeros first, then ones, and finally all twos

In this way, the array must be traversed twice, first for the count of occurrences and second for reassignment, in O(n) time.

Code implementation:

package com.heiz.algorithm.array;

/ * * *@authorHei says Java *@ClassName Sort012
 * @Description
 * @date2021/11/21 * * /
public class Sort012 {

    public static void main(String[] args) {

        int[] a = {1.0.2.0.0.1.2.2.1};
        sort(a);
        for (int val : a) {
            System.out.print(val + ""); }}public static void sort(int[] a) {
        // Save the occurrences of 0,1, and 2
        int[] freq = new int[3];
        for (int val : a) {
            freq[val]++;
        }
        int pointer = 0;
        for (int i = 0; i < freq.length; i++) {
            while (freq[i]-- > 0) { a[pointer] = i; pointer++; }}}}Copy the code

Find the maximum sliding window value

Title description:

Given an array of integers and an integer k, find the largest element from all contiguous subarrays of size k.

Such as:

Input: int[] arr = {2,6,-1,2,4,1,-6,5} int k = 3Copy the code

The corresponding output should be:

Output: 6,6,4,4,4,5Copy the code

So for every subarray of size 3, print the maximum value.

Ideas:

Generate all subarrays of the array according to K, and then iterate to find their maximum value.

This method basically takes the next K elements for each point and iterates to find the maximum. The time complexity of this algorithm is O(n* K).

Code implementation:

package com.heiz.algorithm.array;

/ * * *@authorHei says Java *@ClassName SlidingWindowMax
 * @Description
 * @date2021/11/21 * * /

import java.util.Scanner;

public class SlidingWindowMax {

    public static void main(String[] args) {
        System.out.println("Please enter array size:");
        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        System.out.println("Please enter an array element:");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }
        System.out.println("Please enter window size:");
        int windowSize = scn.nextInt();
        solve(arr, windowSize);

    }

    public static void solve(int[] arr, int k) {
        for (int i = k; i <= arr.length; i++) {
            int max = Integer.MIN_VALUE;

            for (int j = i - k; j < i; j++) {
                max = Math.max(max, arr[j]);
            }

            System.out.print(max +"\t"); }}}Copy the code

Running results:

Idea 2:

Use the Deque to help us find the maximum sliding window in O(n).

A Deque is a double-endian queue, that is, you can add or remove elements from the front or the back.

The way we solve this problem is:

We keep k elements of the subarray in reverse order, we don’t need to keep all K elements, as we’ll see later in the code.

Generate a Deque for the first K elements, keeping them in reverse order so that the largest element comes first.

If the Deque is empty, add elements directly, otherwise check whether the element passed in is greater than the last element, if so, continue popping elements from the last element until the last element of the remaining Deque is greater than the element passed in.

We also need to remove the elements that belong to different subarrays. That is, the subscript of the Deque must be in the range [I, I +k].

Code implementation:

package com.heiz.algorithm.array;

import java.util.LinkedList;
import java.util.Scanner;

/ * * *@authorHei says Java *@ClassName SlidingWindowMax
 * @Description
 * @date2021/11/21 * * /

public class SlidingWindowMax {

    public static void main(String[] args) {
        System.out.println("Please enter array size:");
        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        System.out.println("Please enter an array element:");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }

        System.out.print("arr[]: {");
        for (int j : arr) {
            System.out.print("" + j);
        }
        System.out.println("}");
        System.out.println("Please enter window size:");
        int windowSize = scn.nextInt();

        solveEfficient(arr, windowSize);

    }

    public static void solveEfficient(int[] arr, int k) {
        LinkedList<Integer> deque = new LinkedList<>();

        for (int i = 0; i < arr.length; i++) {

            while(! deque.isEmpty() && arr[deque.getLast()] <= arr[i]) { deque.removeLast(); }while(! deque.isEmpty() && deque.getFirst() <= i - k) { deque.removeFirst(); } deque.addLast(i);if (i >= k - 1) {
                System.out.print(""+ arr[deque.getFirst()]); }}}}Copy the code

Running results: