数组(力扣)

0. 牛客数组输入输出

1.动态容器变数组

ArrayList<Integer> vector = new ArrayList<Integer>();
        while(sc.hasNext()){
            int n = sc.nextInt();
            vector.add(n);
        }
// T[] vector.toArray(T[vector.size()])
// 这里注意下，用到了泛型构造
Integer[] arr = vector.toArray(new Integer[vector.size()]);
System.out.println(findDuplication(arr));

参考资料:
ArrayList to Array Conversion in Java
将ArrayList转换为Array的toArray的方法

1.排序

逆序对

剑指 Offer 51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:
输入: [7,5,6,4]
输出: 5
(7,5) (7,6) (7,4) (5,4) (6,4)

解题思路:
如果用暴力方法，两层循环，统计每次找左侧大于当前数的个数，时间复杂度是O(Nˆ2)。借助merge排序中的函数，可以做到每次排序都扫过一次，快速统计个数，时间复杂度是O(Nlog(N))。

原本要统计每一个数左边比当前数小的数的词频和。现在可以转化成，在当前区间内，它贡献的逆序对数目就是统计右边比它大的数，可以一次统计完。借助merge函数左右开弓加速统计, 根据分治的思想，先统计左右区间的逆序对和最后再加上左右区间合并中产生的逆序对和。

另外要特别注意的是，如果左右区间有相等的元素时，优先移动右侧区间的指针，因为如果移动左侧的，右侧下一个数比之前左侧的大就没有统计上，比如[1,3,2,3,1]，统计它的左右区间[1,2,3]和[1,3]，如果先移动左侧的1到3，就无法统计到右侧的2大于左侧的1的逆序对。上述核心思想代码就是:

// 如果右边p1大于左边p2，说明一次就可以统计m-p1+1个逆序对
// 因为arr[p1]大于arr[p2]，且arr[p1+1~m]都会大于arr[p2]
if (arr[p1] > arr[p2]){
    res += m-p1+1;
}

// 统计左半部分的逆序对 + 右半部分的逆序对 + 合并左右部分时产生的逆序对
return process(arr, l, m) + process(arr, m+1, r) + merge(arr, l, m, r);

图片说明

public static int reversePairs(int[] nums){
    if (nums==null || nums.length==1){
        return 0;
    }
    return process(nums, 0, nums.length-1);
}

public static int process(int[] arr, int l, int r){
    // base case, 只有一个元素没有逆序对
    if (l==r){
        return 0;
    }
    int m = l + ((r-l)>>1);
    // 统计左半部分的逆序对 + 右半部分的逆序对 + 合并左右部分时产生的逆序对
    return process(arr, l, m) + process(arr, m+1, r) + merge(arr, l, m, r);
}

public static int merge(int[] arr, int l, int m, int r){
    // 辅助数组
    int[] help = new int[r-l+1];
    int p1 = l;
    int p2 = m+1;
    int index = 0;
    // 统计逆序对的数目
    int res = 0;

    while (p1<=m && p2<=r){
        // 如果右边p1大于左边p2，说明一次就可以统计m-p1+1个逆序对
        // 因为arr[p1]大于arr[p2]，且arr[p1+1~m]都会大于arr[p2]
        if (arr[p1] > arr[p2]){
            res += m-p1+1;
        }
        help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    }

    while (p1<=m){
        help[index++] = arr[p1++];
    }

    while (p2<=r){
        help[index++] = arr[p2++];
    }

    for (int i = 0; i < index; i++) {
        arr[l+i] = help[i];
    }
    // 返回逆序对数目
    return res;
}

2.词频统计

找出数组中重复的数字

JZ 03
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

解法一: 先排序后遍历
在数据的题中，排序是一个非常好的辅助手段
时间复杂度: O(nlog(n))
空间复杂度: O(1)

public int findRepeatNumber(int[] nums) {
        // 先排序，再逐一扫描，时间复杂度大，没有额外空间复杂度
        Arrays.sort(nums);
        int pre = nums[0];
        for(int i=0; i<nums.length; i++){
            if(i>0 && pre==nums[i]){
                return pre;
            }
            if(i>0){
                pre = nums[i];
            }
        }
        throw new IllegalArgumentException("no duplicated number!");

    }

解法二: 建立HashSet，检查重复的元素
时间复杂度: O(n)
空间复杂度: O(n), 额外建立了哈希表

public int findRepeatNumber(int[] nums) {
    // 认为建立hashset， 如果有重复的数子，就返回
    HashSet<Integer> set = new HashSet<>();
    for(int elem : nums){
        if(set.contains(elem)){
            return elem;
        }
        set.add(elem);
    }
    throw new IllegalArgumentException("No duplicated number");
}

还可以自己手动建立HashMap, 利用输入数据的特性和桶排序，如果没有重复，每个数据都有自己的下标一致，也就是说，每个桶里面都只有一个数，如果某个桶有两个数，就是重复的数

public boolean duplicate(int array[],int length,int [] duplication) {
    if ( array==null ) return false;

    // 判断数组是否合法（每个数都在0~n-1之间）
    for ( int i=0; i<length; i++ ) {
        if ( array[i]<0 || array[i]>length-1 ) {
            return false;
        }
    }

    // 每个桶都应该有一个数，初始默认每个桶为0
    int[] hash = new int[length];
    for( int i=0; i<length; i++ ){
        hash[array[i]]++;
    }
    for(int i=0; i<length; i++){
        // 大于1，就是有重复的
        if ( hash[i]>1 ) {
            duplication[0] = i;
            return true;
        }
    }
    return false;
}

方法三: 自然哈希表
把数组视为哈希表（有一类问题是这么做的，但是会修改数组）
分析：
这个思路利用到了数组的元素值的范围恰好和数组的长度是一样的，因此数组本身可以当做哈希表来用。遍历一遍就可以找到重复值，但是修改了原始数组。

由于数组元素的值都在指定的范围内，这个范围恰恰好与数组的下标可以一一对应；

因此看到数值，就可以知道它应该放在什么位置，这里数字nums[i] 应该放在下标为 i 的位置上，这就像是我们人为编写了哈希函数，这个哈希函数的规则还特别简单；
时间复杂度: O(n)
空间复杂度: O(1)

public int findRepeatNumber(int[] nums) {
    int len = nums.length;

    for (int i = 0; i < len; i++) {
        // 如果当前的数 nums[i] 没有在下标为 i 的位置上，就把它交换到下标 i 上
        // 交换过来的数还得做相同的操作，因此这里使用 while
        // 可以在此处将数组输出打印，观察程序运行流程
        // System.out.println(Arrays.toString(nums));

        while (nums[i] != i) {

            if (nums[i] == nums[nums[i]]) {
                // 如果下标为 nums[i] 的数值 nums[nums[i]] 它们二者相等
                // 正好找到了重复的元素，将它返回
                return nums[i];
            }
            swap(nums, i, nums[i]);
        }
    }
    throw new IllegalArgumentException("数组中不存在重复数字！");
}

private void swap(int[] nums, int index1, int index2) {
    int temp = nums[index1];
    nums[index1] = nums[index2];
    nums[index2] = temp;
}

3.连续性

数组中最长连续子序列

Nr. 128
给定一个未排序的整数数组，找出最长连续序列的长度。序列可以空间上不连续，但数值连续。

要求算法的时间复杂度为 O(n)。

示例:
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

解题思路：
利用哈希表和并查集合的思路，只去检查之前没有出现的数，这样做到了去重（重复的数对区间扩张无影响）。每个数都有一个所在区间的长度，可以用HashMap记录。
每当新加入数时，检查他的的左邻居和右邻居的值对应的长度。如果左右邻居所对应的长度不为零，就说明可以合并区间，更新长度。

左邻居有值，右邻居无，说明cur在一个大集合的最右边，把cur合并后，大集合右边界加一，对应长度也增加left+1。
左邻居无，右邻居有值，说明cur在一个大集合的最左边，把cur合并后，大集合左边界加一，对应长度也增加right+1。
左右邻居均有值，说明cur在两个大集合的中间，把cur合并后，大集合左右边界加一，对应长度也增加right+left+1。

注意每次更新区间边界时，只需要更新大区间的左边界和右边界，务必保证他们的长度代表整个区间的最新长度。这是因为我们只处理之前没出现的数，如果一个没出现的数能够把某个区间扩大，或者把某两个连续区间连在一起，毫无疑问，只需要map中有关这些区间的最右和最左的长度。

// 求这个最长连续数组的长度
public static int getLengthOfLCS(int[] nums){
    // 思路就是用哈希表 和 类并查集的思想
    if (nums == null){
        return 0;
    }
    // 初始化最大长度
    int maxLength = 0;
    int left = 0;
    int right = 0;
    int curLen = 0;
    // 建议一个hashMap，遍历数组中不由出现在hash表中的数字
    HashMap<Integer, Integer> mapOfLength = new HashMap<>();
    for (int num : nums){
        if (!mapOfLength.containsKey(num)){
            // 查询这个数字的左右邻居是否可以 和 现有的集合合并
            left = mapOfLength.get(num-1) == null ? 0 : mapOfLength.get(num-1);
            right = mapOfLength.get(num+1) == null ? 0 : mapOfLength.get(num+1);

            curLen = left + right + 1;
            // 更新最大长度
            if (curLen > maxLength){
                maxLength = curLen;
            }

            // 更新这个数的所在区间的长度
            mapOfLength.put(num, curLen);
            // 只更新左右边界
            mapOfLength.put(num-left, curLen);
            mapOfLength.put(num+right, curLen);
        }
    }
    return maxLength;
}

数组中最长连续子序列II

题意和上题一致就是请输出一组找到的最长连续子序列。

解题思路：
承接上题的基础，我们可以得到，最后一次的合并造成最长连续子序列的那个数，记做curNum，和最长的长度，记做maxLength。
我们判断curNum这个数的左右邻居是否在HashMap中：

如果都在，说明curNum最后合并了两个区间，子序列最右边是curNum-left
如果只有右邻居在，说明curNum最后合并了一个左边的大区间，子序列最右边是curNum-maxLength+1
如果只有左邻居在，说明curNum最后合并了一个右边的大区间，子序列最右边就是curNum本身

public static int[] getArrOfLCS(int[] nums){
    if (nums == null){
        return null;
    }
    // 初始化最大长度
    int maxLength = 0;
    int left = 0;
    int right = 0;
    // 记录当前长度
    int curLen = 0;
    // 记录当前的数
    int curNum = 0;
    // 建议一个hashMap，遍历数组中不由出现在hash表中的数字
    HashMap<Integer, Integer> mapOfLength = new HashMap<>();
    for (int num : nums){
        if (!mapOfLength.containsKey(num)){
            // 查询这个数字的左右邻居是否可以 和 现有的集合合并
            left = mapOfLength.get(num-1) == null ? 0 : mapOfLength.get(num-1);
            right = mapOfLength.get(num+1) == null ? 0 : mapOfLength.get(num+1);

            curLen = left + right + 1;
            // 更新最大长度
            if (curLen > maxLength){
                maxLength = curLen;
                curNum = num;
            }

            // 更新这个数的所在区间的长度
            mapOfLength.put(num, curLen);
            // 只更新左右边界
            mapOfLength.put(num-left, curLen);
            mapOfLength.put(num+right, curLen);
        }
    }
    // 答案容器
    if (mapOfLength.containsKey(curNum-1) && mapOfLength.containsKey(curNum+1)){
        // 说明最后一个数是中间的，融合了两个区间
        left = curNum-left;
        return getNatureArr(left, maxLength);
    }else if (mapOfLength.containsKey(curNum-1)){
        // 说明最后一个数是最右侧的数
        left = curNum - maxLength + 1;
        return getNatureArr(left, maxLength);
    }else if (mapOfLength.containsKey(curNum+1)){
        left = curNum;
        return getNatureArr(left, maxLength);
    }
    return null;
}

public static int[] getNatureArr(int start, int n){
    // start: 数组起始值；n：数组长度
    //输入起始值，得到[start, start+n-1]的递增自然数组
    int[] arr = new int[n];
    for (int i=0; i<n; i++){
        arr[i] = start;
        start += 1;
    }
    return arr;
}