数据结构与算法---数组、排序---部分排序、有序数组的平方

部分排序

16.16 部分排序

题目：
给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

提示：

0 <= len(array) <= 1000000

大致就是，在一个数组中，找出两个索引，将索引之内的数组进行排序，则整个数组就变为有序，索引相差越小越好

---

思路

需要两个指针：
一个指针作为第一个索引leftPoint = 0;
一个指针作为第二个索引rightPoint = array.length - 1;

遍历数组，当前遍历的指针为currentPoint = 0;

判断当前元素是否为剩余元素的最小值，如果是，则leftPoint++，currentPoint++;
如果不是最小值，则leftPoint确定

倒着遍历，判断当前元素是否为剩余元素的最大值，如果是，则rightPoint–，currentPoint–;
如果不是最大值，则rightPoint确定

什么时候结束？

当leftPoint > rightPoint时，循环遍历结束，且返回[-1, -1];

class Solution {
    public int[] subSort(int[] array) {
        if(array == null || array.length < 2) 
        {
            return new int[] {-1, -1};
        }
        int leftPoint = 0;
        int rightPoint = array.length - 1;

        while(leftPoint < rightPoint){
            if(isMin(array, leftPoint)){
                leftPoint++;
            }else{
                break;
            }
        }

        if(leftPoint == array.length - 1){
            return new int[]{-1, -1};
        }

        while(leftPoint < rightPoint){
            if(isMax(leftPoint, array, rightPoint)){
                rightPoint--;
            }else{
                break;
            }
        }

        if(rightPoint == leftPoint){
            return new int[]{-1, -1};
        }

        return new int[]{leftPoint, rightPoint};
    }

    //判断当前数据是否为剩余数据的最小值
    public boolean isMin(int[] array, int leftPoint)
    {
        int min = array[leftPoint];
        for(int i = leftPoint + 1; i<array.length; i++)
        {
            if(array[i] < min){
                return false;
            }
        }
        return true;
    }

    //判断当前数据是否为剩余数据的最大值
    public boolean isMax(int leftPoint, int[] array, int rightPoint)
    {
        int max = array[rightPoint];
        for(int i = rightPoint - 1; i>=leftPoint; i--)
        {
            if(array[i] > max){
                return false;
            }
        }
        return true;
    }
}

代码在leetCode可以执行，但是时间复杂度高，没有达到题目要求。

时间复杂度

最坏：O(n^2)

能否优化

其实，从左遍历到最右边，不一定是要判断当前是否为最小值

从右到左，找出第一个比leftPoint小的值，如果有，则记录位置，如果没有，则leftPoint++;从新来一遍
从左到右，找出第一个比rightPoint大的值，如果有，则记录位置，如果没有，则rightPoint–;从新来一遍

但有个问题，比如[8, 19, 3, 1, 10]
按照上面的思想：
从左往右，找出第一个比10大的值，可以看出是19，位置为1
从右往左，找出第一个比8小的值，可以看出是1，位置为3
也就是排序[1, 3]的位置[8, 1, 3, 19, 10]，明显不是有序的，因此，这种思路不通

那么，MJ大神用什么思想解题呢？

---

MJ思路

寻找逆序对
寻找最大的逆序对

从左往右，找到最后一个逆序的地方
从右往左，找到最后一个逆序的地方

int max = nums[0];
从左往右遍历：
如果扫描的值 大于或等于 最大值，则将该值设为最大值max = nums[i];currentPoint++;
如果扫描的值 小于 最大值，则记录其位置leftPoint = currentPoint;currentPoint++;

从右往左遍历，返过来即可

class Solution {
    public int[] subSort(int[] array) {
        if(array == null || array.length < 2) 
        {
            return new int[] {-1, -1};
        }
        int leftPoint = -1;
        int rightPoint = -1;

        int max = array[0];
        for(int i = 0; i<array.length; i++)
        {
            if(array[i] >= max)
            {
                max = array[i];
            }else{
                rightPoint = i;
            }
        }

        int min = array[array.length - 1];
        for(int i = array.length - 1; i >= 0; i--)
        {
            if(array[i] <= min)
            {
                min = array[i];
            }else{
                leftPoint = i;
            }
        }
        return new int[]{leftPoint, rightPoint};
    }

    
}

时间复杂度

O(n)

终于在只听MJ的思路情况下，自己把代码写出来了。
想起一句话：
一杯茶，一包烟，一道算法解一天
简直了

---

有序数组的平方

977 有序数组的平方

给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：[-4,-1,0,3,10]
输出：[0,1,9,16,100]

示例 2：

输入：[-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A 已按非递减顺序排序。

---

思路

第一想法是，求出数组A中每一个元素的平方值，然后再进行从小到大的排序
时间复杂度：遍历数组求平方O(n) + 排序O(nlogn)
空间复杂度：排序的空间复杂度

第二个想法是，求出数组A的绝对值，然后从小到大排序，再依次求出平方，就是所要的结果。
时间复杂度：遍历数组求绝对值O(n) + 排序O(nlogn)+遍历数组求平方O(n)
空间复杂度：排序的空间复杂度

有个潜在的条件没有使用，就是：A已经是有序

可以想到：
第一步，将A数组中的负数，取绝对值变为正数，然后进行从小到大的排序形成新的数组B，这时候的排序就简单了，时间复杂度为O(k)（k为负数的个数）。B的长度为A的长度，其余没有元素的位置置为0

将剩下的正数数组，拿过来形成新的数组C
这就转化为合并两个有序的数组B和C，其中，B和C都是有序的，然后B的长度足够盛放C的数据。