Java实现关于数组的一些骚操作

矫情吗；* 2022-05-17 22:35 178阅读 0赞

## 如何找出数组中唯一的重复元素？ ##

> 问题描述：数组a\[N\]，1-N-1这N-1个数存放在a\[N\]中，其中某个数字重复1次。写一个函数，找出重复的数字。要求每个数组元素只能访问一次，并且不用辅助空间。

分析：由于不能使用辅助物理空间且每个元素只能访问一次，所以可以从原理入手，采用数学求和法。  
设重复的数字为A，那么数组的和为1-N-1，A的累加，减去1-N-1的累加即可得到重复的数字A

public static int findDump(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int sumA = 0;
            int sumN = 0;
            for (int i = 0; i < a.length-1; i++) {
                sumA += a[i];
                sumN += (i+1);
            }
            sumA += a[a.length-1];
            return sumA - sumN;
        }

引申：  
如果放宽限制，比如说可以使用辅助空间，每个元素的遍历次数也不限  
思路1：异或  
（1-N-1，A）^(1-N-1) = A

public static int findDumpWithSpace1(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int result = 0;
            for (int i = 0; i < a.length; i++) {
                result ^= a[i];
            }
            for (int i = 1; i < a.length; i++) {
                result ^= i;
            }
            return result;
        }

思路2：位图法，利用辅助数组记录出现次数

public static int findDumpWithSpace2(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int n = a.length;
            int[] appear = new int[n];
            for (int i = 0; i < n; i++) {
                int curr = a[i];
                if (appear[curr] == 1)
                    return curr;
                else
                    appear[curr] ++;
            }
            return Integer.MAX_VALUE;
        }

思路3：诡异的类似链表有环算法  
![这里写图片描述][70]

## 如何用递归求得数组中的最大值？ ##

> 常用思路：遍历数组，用一个变量记录当前所走过元素的最大值  
> 递归求数组最大值，相当于从末尾开始遍历数组

public static int findMaxNumRecursive(int[] a,int k){
            if (k == a.length -1)
                return a[k];
            int curr = findMaxNumRecursive(a,k+1);
            return Math.max(curr,a[k]);
        }

# 如何求数对之差的绝对值？ #

> 问题描述：数组中一个数字减去它右边子数组中的一个数字可以得到一个差值，求所有可能得差值中的最大值，例如，数组\{1,4,17,3,2,9\}中，最大差值为17-2=15

思路1：蛮力法 。两层遍历，找出所有可能得差值，其次从所有差值中找出最大值。具体实现方法为：针对数组a中的每个元素a\[i\]（0

public static int getMaxSub1(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int max = 0;
            int len = a.length;
            for (int i = 0; i < len; i++) {
                for (int j = i+1; j < len; j++) {
                    int diff = a[i] - a[j];
                    max = Math.max(max,diff);
                }
            }
            return max;
        }

思路2：动态规划  
动态规划真是解决问题好手，可是思路很难想啊喂  
给定数组a，申请额外的数组diff和max，其中diff\[i\]是以数组中第i个数字为减数的所有数对之差的最大值（前i+1个数组成的子数组中的最大的差值），max\[i\]为前i+1个数的最大值。假设已经求得了diff\[i\]，diff\[i+1\]的值有两种可能性：①等于diff\[i\]；②等于max\[i-1\]-a\[i\]。通过上面的分析，可以得到动态规划的计算表达式为：diff\[i+1\] = max(diff\[i\],max\[i-1\]-a\[i\])，max\[i+1\]=max(max\[i\],a\[i+1\])。数组最大差值为diff\[n-1\]（n为数组的长度)

public static int getMaxSub2(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int len = a.length;
            int[] diff = new int[len];
            int[] max = new int[len];
            diff[0] = 0;
            max[0] = a[0];
            for (int i = 1; i < len; i++) {
                diff[i] = Math.max(diff[i-1],max[i-1]-a[i]);
                max[i] = Math.max(max[i-1],a[i]);
            }
            return diff[len-1];
        }
        //动态规划改进：无需数组，只需两个变量，记录上一个最大的差值和最大的数组记录
        public static int getMaxSub3(int[] a){
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int len = a.length;
            int diff = 0;
            int max = a[0];
            for (int i = 0; i < len; i++) {
                diff = Math.max(diff,max-a[i]);
                max = Math.max(max,a[i]);
            }
            return diff;
        }

思路3：二分法  
通过二分法可以减少计算的次数。思路如下：把数组分为两个子数组，那么最大差值只有3种可能：①最大的差值对应的被减数和减数都在左子数组中，假设最大差值为leftMax；②被减数和减数都在右子数组中，假设最大差值为rightMax；③被减数是左子数组的最大值，减数是右子数组中的最小值，假设差值为minMax。那么就可以得到这个数组的最大差值为这3个差值的最大值，即max(leftMax,rightMax,mixMax)。

引申：这道题还可以用求最大子数组之和的方法来解决  
思路：给定一个数组a（数组长度为n），额外申请一个长度为n-1的数组diff，数组diff中的值满足diff\[i\] = a\[i\]-a\[i+1\]，那么a\[i\]-aj就等价于diff\[i\]+diff\[i+1\]+diff\[i+2\]+…..+diff\[j\]。所以，求所有a\[i\]-a\[j\]组合的最大值就可以转换为求解所有diff\[i\]+diff\[i+1\]+…+diff\[j\]组合的最大值。由于diff\[i\]+diff\[i+1\]+…+diff\[j\]代表diff的一个子数组，因此可以用求最大子数组之和的方法来解决

# 如何求绝对值最小的数？ #

> 问题描述：有一个升序的数组，数组中可能有正数、负数或0，求数组中元素的绝对值最小的数，例如，数组\{-10,05,-2,7,15,50\}，绝对值最小的是-2

思路：如果全是非正数，那么最后一个元素的绝对值最小；如果全是非负数，那么最后一个元素的绝对值最大。数组中既有正数，又有负数，通过二分法寻找正数与负数的分界点，如果分界点为0，那么0就是绝对值最小的数，否则通过比较分界点左右正数与负数的绝对值来确定最小的数

public static int getMinAbsoluteValue(int[] a) {
            if (a == null || a.length == 0)
                return Integer.MAX_VALUE;
            int len = a.length;
            if (a[0] >= 0)
                return a[0];
            if (a[len - 1] <= 0)
                return a[len - 1];
            int begin = 0;
            int end = len-1;
            int mid = 0;
            while (true){
                mid = (begin+end) >> 1;
                if (a[mid] == 0)
                    return a[mid];
                else if (a[mid] > 0){
                    if (mid > 0 && a[mid-1] == 0)
                        return a[mid-1];
                    else if (mid > 0 && a[mid-1] > 0){
                        end = mid-1;
                    }else   //找到正负分界点
                        break;
                }else {
                    if (mid < len-1 && a[mid+1] == 0)
                        return a[mid+1];
                    else if (mid < len-1 && a[mid+1] < 0 )
                        begin = mid+1;
                    else  //找到正负分界点
                        break;
                }
            }
            if (a[mid] > 0){
                if (Math.abs(a[mid-1]) > a[mid])
                    return a[mid];
                else
                    return a[mid-1];
            }else{
                if (Math.abs(a[mid]) > a[mid+1])
                    return a[mid+1];
                else
                    return a[mid];
            }
        }

# 如何求数组中两个元素的最小距离？ #

> 问题描述：给定一个数组，数组中含有重复的元素，给出两个数n1,n2，求这两个数字在数组中所出现位置的最小距离  
> 例如数组\{4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8\}中，4和8的最小距离为2

思路：  
①遇到n1时，记录n1对应的数组下标位置index1，通过求index1与上次遍历遇到n2的下标值index2的差，可以求出最近一次遍历到的n1与n2的距离  
②遇到n2时，记录n2对应的数组下标的位置index2，然后通过求index2与上次遍历遇到n1的下标值index1的差，可以求出最近一次遍历到的n1与n2的距离

public static int minDistance(int[] a,int n1,int n2){
            if (a == null || a.length == 0)
                return -1;
            int len = a.length;
            int index1 = -1;
            int index2 = -1;
            int minDis = Integer.MAX_VALUE;
            for (int i = 0; i < len; i++) {
                if (a[i] == n1){
                    index1 = i;
                    if (index2 > 0) {
                        minDis = Math.min(Math.abs(minDis), Math.abs(index1 - index2));
                    }
                }
                if (a[i] == n2){
                    index2 = i;
                    if (index1 > 0) {
                        minDis = Math.min(Math.abs(minDis), Math.abs(index1 - index2));
                    }
                }
            }
            return minDis;
        }

# 如何求指定数字在数组中第一次出现的位置？ #

> 问题描述：给定数组a = \{3,4,5,6,5,6,7,8,9,8\}，这个数组中相邻元素之差都为1，给定数字9，它在数组中第一次出现的位置的下标为8（数组下标从0开始）

思路1：  
蛮力法，遍历数组，依次将数组中的元素与待查找的值比较，如果相等则返回下标位置。  
时间复杂度O(n)，效率不高，而且没有用到题目中的条件：相邻元素之差为1  
思路2：  
跳跃搜索法。假设先从数组a中查找9出现的位置，首先用数组中第一个元素（数组下标为0）3与9进行比较，他们的差值为6，由于数组中相邻两个元素的差值为1，所以9在数组中出现的最早的位置必定为1+6 = 7（数组下标为6）。这是因为：如果数组是递增的，那么数组的第7个元素才为9，如果数组不是递增的，那么9出现的位置肯定在数组的第7个元素后面，可以减少查找的次数。  
从数组的第一个元素开始（i=0），把数组当前位置的值与t进行比较，如果相等，则返回数组下标，否则，从数组下标i+|t-a\[i\]|处继续查找

public static int findIndex(int[] a,int t){
            if (a == null || a.length == 0)
                return -1;
            int len = a.length;
            int i = 0;
            while (i < len){
                if (a[i] == t)
                    return i;
                else {
                    i += Math.abs(t - a[i]);
                }
            }
            return -1;
        }

# 如何对数组的两个子有序段进行合并？ #

> 问题描述：数组a\[0,mid-1\]和a\[mid,n-1\]是各自有序的，对数组a\[0,n-1\]的两个子有序段进行合并，得到a\[0,n-1\]整体有序。要求空间复杂度为O(1)

分析：  
由于限定空间复杂度为O(1)，所以不能使用归并方法。最容易想到的就是插入排序方法，这种算法的时间复杂度是O(n^2)，空间复杂度为O(1)，能满足题目要求，但由于插入排序没有用到”数组a\[0,mid-1\]和a\[mid,n-1\]是各自有序的“这个条件，所以这并不是最好的算法。  
实现思路：  
首先，遍历数组中下标中0-mid-1的元素，将遍历到的元素的值与a\[mid\]进行比较，当遍历到a\[i\]（0 <= i <= mid-1）时，如果满足a\[mid\] < a\[i\]，那么交换a\[i\]与a\[mid\]的值，接着找到交换后的a\[mid\]在a\[mid,num-1\]中的具体位置（在a\[mid,num-1\]中进行插入排序），实现方法为：遍历a\[mid-num-2\]，如果a\[mid+1\] < a\[mid\]，那么交换a\[mid\]与a\[mid+1\]的位置

public static void mergeTwoArrayWithNoSpace(int[] a,int mid){
            if (a == null || a.length == 0 || mid < 0 || mid > a.length-1)
                return;
            for (int i = 0; i < mid; i++) {
                if (a[mid] < a[i]){
                    int tmp = a[mid];
                    a[mid] = a[i];
                    a[i] = tmp;
                    findRightPlaceForMid(a,mid);
                }
            }
        }
        private static void findRightPlaceForMid(int[] a,int mid){
            boolean flag = true;
            for (int i = mid; i < a.length - 1 && flag; i++) {
                flag = false;
                if (a[i+1] < a[i]){
                    flag = true;
                    int tmp = a[i];
                    a[i] = a[i+1];
                    a[i+1] = tmp;
                }
            }
        }

# 如何计算两个有序整数数组的交集？ #

> 问题描述：两个有序数组（非降序）a和b，其中a=\{0,1,2,3,4\}，b = \{1,3,5,7,9\}，那么它们的交集为\{1,3\}

*  长度相当的数组：

①依次从头遍历两个数组，遇到相同的则后移指针，如果其中一个记录大，则后移记录小的数组的指针，直到一个数组遍历结束

public static ArrayList<Integer> Mixed1(int[] a1,int[] a2){
            ArrayList<Integer> result = new ArrayList<>();
            if (a1 == null || a2 == null || a1.length == 0 || a2.length == 0)
                return result;
            int index1 = 0;
            int index2 = 0;
            int len1 = a1.length;
            int len2 = a2.length;
            while (index1 < len1 && index2 < len2){
                if (a1[index1] == a2[index2]){
                    result.add(a1[index1]);
                    index1++;
                    index2++;
                }else if (a1[index1] < a2[index2])
                    index1++;
                else
                    index2++;
            }
            return result;
        }

②利用哈希表，先将一个数组中的记录保存在哈希表中，然后遍历另一个数组，判断其中的记录是否在哈希表中，如果在哈希表中则证明属于交集

public static ArrayList<Integer> Mixed2(int[] a1,int[] a2){
            ArrayList<Integer> result = new ArrayList<>();
            if (a1 == null || a2 == null || a1.length == 0 || a2.length == 0)
                return result;
            Map<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < a1.length; i++) {
                map.put(a1[i],1);
            }
            for (int i = 0; i < a2.length; i++) {
                if (map.containsKey(a2[i]))
                    result.add(a2[i]);
            }
            return result;
        }

③顺序遍历两个数组，保存记录及其数量到哈希表中，如果出现的次数为2则是交集中的元素  
长度相差悬殊的情况

[70]: /images/20220518/b9ab49c1acb447aa80e2f0ad9e382c52.png