【算法系列】Array算法题详细解析(续)

发表于

这是我参与11月更文挑战的第22天，活动详情查看：2021最后一次更文挑战

我是小黑，一个在互联网“苟且”的程序员。

流水不争先，贵在滔滔不绝

本期内容是对上一期【算法系列】Array算法题详细解析的一个延伸，主要包含三道数组相关算法题目的解题思路和代码实现。

将数组中的奇数和偶数分开

题目描述：

给定一个整数数组，将数组中的奇数和偶数分开。元素的顺序可以改变。

思路：

  • 假设数组是arr[]
  • 初始化两个索引变量，left=0,right=arr.length-1
  • 递增left变量知道数值为奇数
  • 递减right变量直到数值为偶数
  • 如果left<right，将arr[left]和arr[right]交换
  • 最后的结果左边是偶数，右边是奇数

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
java复制代码package com.heiz.algorithm.array;

/**
 * @author 小黑说Java
 * @ClassName SeparateOddEvenMain
 * @Description
 * @date 2021/11/21
 **/
public class SeparateOddEvenMain {

    public static void main(String[] args) {

        int[] arr = {12, 17, 70, 15, 22, 65, 21, 90};
        System.out.println("原始数组: ");
        for (int j : arr) {
            System.out.print(j + " ");
        }
        separateEvenOddNumbers(arr);
        System.out.println("\n奇数和偶数分开后数组: ");
        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) {
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
    }
}

运行结果：

对一个只有012的数组用O(n)时间复杂度排序

题目描述：

现有整数数组，其内部元素只有0,1,2，例如：int[] arr = [1, 2, 2, 0, 0, 1, 2, 2, 1]，对其进行排序，要求为O(1)时间复杂度。

思路：

因为数组中只有数字012，所以先遍历一遍数组，记录下0,1,2出现的次数，然后重新遍历一遍数组，按照012出现的次数重新对数组中的元素赋值。

步骤:

  • 遍历给定数组一次，并不断增加所遇到的数字的计数。
  • 再次遍历数组，从索引0开始，不断改变当前索引上元素的值，首先耗尽所有的0，然后是1，最后是所有的2

这种方式必须对数组遍历两次，第一次为统计出现次数，第二次重新赋值，时间复杂度为O(n)。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
java复制代码package com.heiz.algorithm.array;

/**
 * @author 小黑说Java
 * @ClassName Sort012
 * @Description
 * @date 2021/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) {
        // 保存0,1,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++;
            }
        }
    }
}

查找滑动窗口最大值

题目描述：

给定一个整数数组和一个整数k，从所有大小为k的连续子数组中找出最大元素。

比如：

1
2
shell复制代码Input : int[] arr = {2,6,-1,2,4,1,-6,5}
int k = 3

则对应的输出结果应该是：

1
shell复制代码output : 6,6,4,4,4,5

也就是对每一个大小为3的子数组，打印其中的最大值。

思路：

将数组按照K生成所有的子数组，然后遍历找出他们的最大值。

这种方式对于每个点基本都是取下一个K个元素，然后遍历，找到最大值，这个算法的时间复杂度为O(n*k)。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
java复制代码package com.heiz.algorithm.array;

/**
 * @author 小黑说Java
 * @ClassName SlidingWindowMax
 * @Description
 * @date 2021/11/21
 **/

import java.util.Scanner;

public class SlidingWindowMax {

    public static void main(String[] args) {
        System.out.println("请输入数组大小：");
        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        System.out.println("请输入数组元素：");
        for (int i = 0; i < arr.length; i++) {
            arr[i] = scn.nextInt();
        }
        System.out.println("请输入窗口大小：");
        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");
        }
    }
}

运行结果：

思路二：

使用Deque来帮助我们找到O(n)中滑动窗口的最大值。

Deque是一个双端队列，也就是说，你可以从前面或后面添加或删除元素。

我们解决这个问题的方法是:

我们保留子数组的k个元素以相反的顺序，我们不需要保留所有的k个元素，我们将在后面的代码中看到。

为前k个元素生成Deque，保持它们的倒序，以便最大的元素在前面。

如果Deque是空的，直接添加元素，否则检查传入的元素是否大于最后一个元素，如果是，继续从最后一个元素弹出元素，直到剩余Deque的最后一个元素大于传入的元素。

我们还需要删除属于不同子数组的元素。即Deque的下标必须在[i, i+k]范围内。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
java复制代码package com.heiz.algorithm.array;

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

/**
 * @author 小黑说Java
 * @ClassName SlidingWindowMax
 * @Description
 * @date 2021/11/21
 **/

public class SlidingWindowMax {

    public static void main(String[] args) {
        System.out.println("请输入数组大小：");
        Scanner scn = new Scanner(System.in);
        int[] arr = new int[scn.nextInt()];
        System.out.println("请输入数组元素：");
        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("请输入窗口大小：");
        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()]);
            }

        }
    }
}

运行结果：

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%