最长的可整合子数组的长度

题目描述

先给出可整合数组的定义：如果一个数组在排序之后，每相邻两个数的绝对值都为1，或者该数组长度为1，则该数组为可整合数组。例如[5,3,4,6,2]排序后为[2,3,4,5,6],符合每相邻两个数差的绝对值都为1，所以这个数组为可整合数组。给定一个数组arr，请返回其中最大可整合子数组的长度。例如[5,5,3,2,6,4,3]的最大可整合子数组为[5,3,2,6,4],所以请返回5
[要求]时间复杂度为O(n^2),空间复杂度为O(n)

输入示例
7
5 5 3 2 6 4 3
输出
5

解题思路分析

• 首先本题题意描述可整合数组的定义得清晰，而且题目也给了提示了，其实得先给数组进行排序
• 使用快排排完序之后呢，我们就要考虑如何在排序数组中给找出最长的可整合子数组的长度，这里可以使用双指针法进行查找（代码中有了详细介绍了）

代码实现

public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = Integer.valueOf(scanner.nextLine());
        int[] nums = new int[n];
        String[] lines = scanner.nextLine().split(" ");
        for (int i = 0; i < n; i++) {
            nums[i] = Integer.valueOf(lines[i]);
        }
        quickSort(nums, 0, n - 1);
        System.out.println(getAns(nums, n));
    }
    //快排
    private static void quickSort(int[] nums, int left, int right) {
        int base = nums[left], i = left, j = right;
        while (i < j) {
            while (nums[j] >= base && i < j) {
                j--;
            }
            if (i < j) {
                nums[i] = nums[j];
                i++;
                while (nums[i] <= base && i < j) {
                    i++;
                }
                if (i < j) {
                    nums[j] = nums[i];
                    j--;
                }
            }
        }
        nums[i] = base;
        if (left < (i - 1)) {
            quickSort(nums, left, i - 1);
        }
        if ((j + 1) < right) {
            quickSort(nums, j + 1, right);
        }
    }

    private static int getAns(int[] nums, int n) {
        /**
         * 初始长度肯定为 1 ，因为最长子整合数组中至少会有一个元素，然后定义两个下标 i 为前面这个下标，j 为后面这个下标
         */
        int length = 1, i = 0, j = 1;
        while (i < n && j < n) {//停止条件为 i 和 j 都不越界
            if (j < n - 1) {//首先得判断 j 是否到了数组的最后一个位置，在这里判断是为了后面不会抛出越界异常
                if (nums[j] == nums[j + 1]) {//如果 j 与 j 后面这个数字相等时，就可以直接将 j 定位到后面这个数字，此时 i 不变
                    j++;
                } else if (nums[i] == (nums[j] - 1)) {// 当前 i 和 j 指向的数字符合题目要求
                    length++;//长度 +1
                    j++;// j 后移一位
                    i = j - 1;//注意这里需要始终保证 i 和 j 相邻
                } else {// 当前 j 和 i 指向的数字不符合题目要求
                    j++;// j 后移一位
                    i = j - 1;//注意这里需要始终保证 i 和 j 相邻
                }
            } else {// j 指向了最后一个数字
                if (nums[i] == (nums[j] - 1)) {//如果此时符合要求
                    length++;//长度 +1
                    j++;// j 后移一位
                    i = j - 1;//注意这里需要始终保证 i 和 j 相邻
                } else {//不符合要求
                    j++;// j 后移一位
                    i = j - 1;//注意这里需要始终保证 i 和 j 相邻
                }
            }
        }
        return length;
    }