数组相关算法

发表于 | 分类于 | | 阅读次数

寻找数组中最小值与最大值。

方法一：维持2个变量min与max，每次取一个元素分别与两个变量比较，最后通过一次数组遍历找到最大值与最小值，虽然时间复杂度是O（n）但是比较次数是2.
方法二：维持2个变量min和max,每次取相邻的两个数，较大者和max比，较小者和min比，以这样的方式找到最大值与最小值，时间复杂度为O（n/2）=O(n),但是比较次数为1.5N
方法三：分治法。
方法二代码如下：

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
public class MaxAndMin {
    static int max;
    static int min;
    public static void getMaxAndMin(int[] a){
        max = a[0];
        min = a[0];
        int n = a.length;
        for (int i = 1; i < n-1; i=i+2) {
            if(i+1>n){
                if (a[i]>max)
                    max = a[i];
                if (a[i]<min)
                    min = a[i];
            }
            if (a[i]>a[i+1]){
                if (a[i]>max)
                    max = a[i];
                if (a[i+1]<min)
                    min = a[i+1];
            }
            if (a[i]<a[i+1]){
                if (a[i+1]>max)
                    max = a[i+1];
                if(a[i]<min)
                    min = a[i];
            }
        }
    }
    public static void main(String[] args){
        int[] a = {7,3,19,40,4,7,1};
        getMaxAndMin(a);
        System.out.println("Max=" + max);
        System.out.println("Min=" + min);
    }
}

找出数组中第二大的数

方法一：可以用快排将里面的数进行排序，时间复杂度O(nlogn)，然后根据下标遍历数组，时间复杂度O(n),所以总的时间复杂度为O(nlogn)。
方法二：可用两个变量分别记录最大值与第二大值，若出现新变量比最大值大那么第二大值记录原最大值，最大值记录新变量，如果比最大变量小，那么直接与第二大变量比较大小，这样遍历一遍数组就可以得到第二大数。
方法二代码如下：

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
public class SecondMax {
    public static int findSecMax(int[] data){
        int count = data.length;
        int max_Number = data[0];
        int sec_Number = Integer.MIN_VALUE;
        for (int i = 1 ; i < count; i++) {
            if (data[i]>max_Number)
            {
                sec_Number = max_Number;
                max_Number = data[i];
            }else {
                if (data[i]>sec_Number){
                    sec_Number = data[i];
                }
            }
        }
        return sec_Number;
    }
    public static void main(String[] args){
        int[] arry = {7,3,19,40,4,7,1,2};
        System.out.println(findSecMax(arry));
    }
}

如何求最大子数组之和（动态规划）

方法一：暴力法，时间复杂度O(n^2)代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MaxSubArray {
    public static void main(String[] args){
        int[] a = {1,-2,4,8,-4,7,-1,5};
        System.out.println(maxSubArrayMethod1(a));
    }
     private static int maxSubArrayMethod1(int[] a) {
        int size = a.length;
        int max_sum = 0;
        for (int i = 0; i < size; i++) {
            int sum = 0;
            for (int j = i; j < size; j++) {
                sum += a[j];
                if (sum>max_sum){
                    max_sum = sum;
                }
            }
        }
        return max_sum;
    }

方法二：动态规划法思路如下：
1.最大子数组包含arr[n-1],即是以数组最后一个元素arr[n-1]结尾。
2.arr[n-1]自己单独构成最大数组。
3.最大数组不包含arr[n-1]，那么求arr[1,…,n-1]的最大子字符串可以转换为求arr[1,…,n-2]的最大子字符串。
通过以上可以的出结论，架设已经计算出（arr[0],…,arr[i-1]）最大的一段数组和为ALL[i-1]，同时也计算出（arr[0],…,arr[i-1]）中包含arr[i-1]的最大的一段数组和为End[i-1]。则可以得出如下关系ALL[i-1] = max {arr[i-1],End[i-1],arr[i-2]}。利用这个公式和动态规划的思想可以得出如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class MaxSubArray {
    public static void main(String[] args) {
        int[] a = {1, -2, 4, 8, -4, 7, -1, -5 };
        System.out.println(maxSubArrayMethod2(a));
    }
    public static int max(int m, int n) {
        return m > n ? m : n;
    }
    private static int maxSubArrayMethod2(int[] a) {
        int n = a.length;
        int End[] = new int[n];
        int All[] = new int[n];
        End[n - 1] = a[n - 1];
        All[n - 1] = a[n - 1];
        End[0] = All[0] = a[0];
        for (int i = 1; i < n; i++) {
            End[i] = max(End[i - 1]+a[i], a[i]);
            All[i] = max(End[i], All[i - 1]);
        }
        return All[n - 1];
    }
}

上文的动态规划方法可以优化因为每次只用到End[i-1]与All[i-1]而不是整个数组中的值，所以可以定义两个变量来保存End[i-1]与All[i-1]的值，并且可以反复利用，
这样就可以保证在时间复杂度为O(n)的同时降低空间复杂度。
只要nEnd=max(nEnd+arr[i],arr[i]); nAll=max(nEnd,nALL); 替换上文的如上代码即可。

知道子数组的最大和之后，如何确定最大子数组的位置？为了得到最大的子数组，从公式End[i]=max(End(i-1)+a[i],a[i])的分析可以看出，
当End[i-1]<0的时候，End[i]=a[i],其中End[i]表示包含a[i]的子数组和，如果某一个值是的End[i-1]<0,那么就从a[i]位置重新开始编号。

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
public class MaxSubArrayIndex {
    private static int begin = 0;
    private static int end = 0;
    public static void main(String[] args){
        int[] a = {1,-2,4,8,-4,7,-1,-5};
        System.out.println("max=" + maxSubway(a));
        System.out.println("begin=" + begin + " end=" + end);
    }
    public static int maxSubway(int a[] ){
        int maxSum = Integer.MIN_VALUE;//子数组的最大值
        int nSum = 0;//包含子数组最后一位的最大值
        int nStart = 0;
        for (int i = 0; i < a.length; i++) {
            if (nSum<0){
                nSum = a[i];
                nStart = i;
            }else {
                nSum += a[i];
            }
            if (nSum > maxSum){
                maxSum = nSum;
                begin = nStart;
                end = i;
            }
        }
        return maxSum;
    }
}

如何找到数组中重复最多的元素

对于数组{1,1,2,2,4,4,4,4,5,5,6,6,6},元素1出现的次数为2，元素2出现次数为2，元素4出现次数为4,5出现次数2,6出现次数3。找出数组中出现重复次数最多的数。
上述问题中，程序的输出应该为元素4。
方法一：空间换时间。定义一个数组int count[MAX]先都初始化为0，然后每次遇到a[i]，那么cout[a[i]]++。之后找到count中值最大的，即是要找的数值。
方法二：使用Map映射表。Map中第一个字记录值为关键字，第二个字记录出现次数。
方法二代码如下：

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
public class MostFrequentInArray {
    public static void main(String[] args){
        int a[] = {1,1,2,2,4,4,4,4,5,5,6,6,6};
        int max_frequent = findMostFrequent(a);
        System.out.println(max_frequent);
    }
    private static int findMostFrequent(int[] a) {
        int result = 0;
        int n = a.length;
        if(0==n)
            return Integer.MAX_VALUE;
        //记录给个元素出现的次数
        Map<Integer,Integer> m = new HashMap<Integer, Integer>();
        for (int i = 0; i < n; i++) {
            if (m.containsKey(a[i])){
                m.put(a[i],m.get(a[i])+1);
            }else {
                m.put(a[i],1);
            }
        }
        //找出出现次数最多的元素
        int most = 0;
        Iterator iterator = m.entrySet().iterator();
        while (iterator.hasNext()){
            Map.Entry entry = (Map.Entry)iterator.next();
            int key = (Integer)entry.getKey();
            int val = (Integer)entry.getValue();
            if (val>most){
                result = key;
                most = val;
            }
        }
        return result;
    }
}

如何求数组中两两相加等于20的组合种类

给定一个数组{1,7,17,2,6,3,14}，这个数组中满足条件的有两组 17+3=20,6+14=20。
方法一：蛮力法用双重循环遍历数组来判断两个数之和是否是20。时间复杂度为O(n^2)。
方法二：排序法先对数组进行排序，可以用堆排序或者快速排序，时间复杂度O(nlogn)，然后对数组从前到后和从后向前遍历，假设从前向后遍历的下标为begin，从后往前的下标为end，如果arr[begin]+arr[end]<20，那么如果存在两个数的和为20，那么这两个数一定在[begin+1,end]之间，当满足arr[begin]+arr[end]>20时，如果存在两个数的和为20，那么这两个数一定在[begin,end-1]之间，这个过程时间复杂度为O(n),因此整个算法的时间复杂度为O(nlogn)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class FindSum {
    public static void main(String[] args){
        int arr[] = {1,7,17,2,6,3,14};
        find(arr,20);
    }
    private static void find(int[] arr,int sum) {
        Arrays.sort(arr);
        int begin = 0;
        int end = arr.length - 1;
        while (begin<end){
            if(arr[begin]+arr[end]<sum)
                begin++;
            else if(arr[begin]+arr[end]>sum)
                end--;
            else {
                System.out.println(arr[begin] + " " + arr[end]);
                begin++;
                end--;
            }
        }
    }
}

如何把一个数组循环右移k位

假设要把数组序列12345678右移2位变为78123456。比较移位前后数组序列的形式，不难看出，其中两段的序列是不变的，即78和123456。可以把这两段看做整体，右移k位就是把数组两部分交换一下，鉴于此，可以设计这样一种算法，步骤如下：
1.逆序数组子序列123456，数组序列的形式变为65432178。
2.逆序数组子序列78，数组序列的形式变为65432187。
3.全部逆序，数组序列的形式变为78123456。
该算法进行了3次逆序操作，因此时间复杂度为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
public class ShiftK {
    public static void main(String[] args){
        int arr[] = {1,2,3,4,5,6,7,8};
        shift_k(arr,2);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i] + " ");
        }
    }
    private static void shift_k(int[] a, int k) {
        int n = a.length;
        k = k % n;
        reverse(a,n-k,n-1);
        reverse(a,0,n-k-1);
        reverse(a,0,n-1);
    }
    public static void reverse(int[] a,int b,int e){
        for (;b<e;b++,e--){
            int temp = a[e];
            a[e] = a[b];
            a[b] = temp;
        }
    }
}

找出数组中第K个最小的数

给定一个无序的数组，从一个数组中找出第K个最小的数。对于给力定数组序列{1,5,2,6,8,0,6}，其中第4小的数为5.
方法一：最简单的方法是对数组进行排序，排序后的数组中第k-1个位置的数字即为数组的第k个最小的数，最好的时间复杂度为O(nlogn)。
方法二：剪枝法，运用快排的思想选定一个数tmp=a[n-1]作为枢纽，把比它都小的数放在它的左边，把比它大的数放在它的右边，然后判断tmp的位置。如果他的位置是k-1，那么他就是第K小的数。如果它的位置小于k-1，那么说明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
public class GetKMin {
    public static void main(String[] args){
        int a[] = {1,5,2,6,8,0,6};
        int k_min = getKMinNumber(a,4);
        System.out.print(k_min);
    }
    public static int quickSort(int a[],int low,int high,int k){
        int i,j;
        int tmp;
        i = low+1;
        j = high;
        tmp = a[i];
        while (i<j){
            while(i<j && a[j]>tmp)
                j--;
            while (i<j && a[i]<tmp)
                i++;
            if(i<j){
                int t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
        a[low] = a[i];
        a[i] = tmp;
        if(i+1==k)
            return tmp;
        else if(i+1>k)
            return quickSort(a,low,i-1,k);
        else
            return quickSort(a,i+1,high,k);
    }
    private static int getKMinNumber(int[] a, int i) {
        return quickSort(a,0,a.length-1,i);
    }
}

如何找出数组中只出现一次的数字

一个整型数组里除了一个数字之外，其他数字都出现两次，找出这个只出现1次的数字。要求时间复杂度为O(n)，空间复杂度O（1）。
如果没有时间复杂度的要求那么可以将数组进行排序，时间复杂度O(nlogn)，然后从第一个数开始遍历，比较相邻的两个数，从而找到这个只出现一次的数字，这种方法复杂度最快为O(nlogn)。由于时间复杂度与空间复杂度的限制，该方法不可取，因此需要一种更高效的方式。题目强调只有一个数字出现1次，其他数字出现了2次，首先想到的是异或运算，因为异或运算的定义，任何一个数字异或它自己都等于0，所以从头到尾一次异或数组中的每一个数字，那些出现两个的都会抵消掉。最终的结果刚好是只出现一次的数。
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class FindNotDouble {
    public static void main(String[] args){
        int arr[] = {1,2,3,2,4,3,5,4,1};
        int num = findNotDoubleNum(arr);
        System.out.print(num);
    }
    private static int findNotDoubleNum(int[] arr) {
        int n = arr.length;
        int result = arr[0];
        for (int i = 1; i < arr.length; i++) {
            result ^= arr[i];
        }
        return result;
    }
}

上述异或运算的方法只适用于其他数字出现的次数为偶数的情况，如果其他数字出现次数为奇数，上述方法不再适用。
如果数组中所有数都出现n次，那么这个数组中的所有数对应的二进制数中各个位上的1出现的个数均可以被n整除。
所以对于本题，架设a只出现一次，那么去除a,后其他所有数字对应的二进制数的每个位置上1的个数为n的倍数。
所以对数组中的所有数组对应二进制数中各个位置上的1的个数对3取余数，就可以得到出现1次的这个数的二进制表示。从而找到这个数。

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
public class FindOnce {
    public static void main(String[] args){
        int arr[] = {1,2,1,2,4,2,4,4,1,3};
        int num = findOnceNum(arr, 3);
        System.out.println(num);
    }
    private static int findOnceNum(int[] arr, int appearTimes) {
        int n = arr.length;
        int []bitCount = new int[32];//int类型的4个字节最多32位
        //计算数组中所有数组对应的二进制数各个位置上出现1的次数。
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < 32; k++) {
                bitCount[k] += ((arr[j]>>k)&1);
            }
        }
        //若某位上的结果不能被整除，则肯定目标数字在这一位上为1
        int appearOne=0;
        for (int j = 0; j < 32; j++) {
            if (bitCount[j]% appearTimes !=0){
                appearOne += (1<<j);
            }
        }
        return appearOne;
    }
}

查找数组中唯一重复的元素

/
数组A[N],1~N-1这个N-1个数存在a[N]中，其中某个数字重复一次。
找出数组中唯一重复的元素
要求每个数只能访问一次并且不用辅助空间 /

1
2
3
4
5
6
7
8
9
10
11
12
13
//方法一累加求和法因为只有一个数重复累加后减去1~N-1的和就是结果
    public static int findDup1(int[] a){
        int n = a.length;
        int sum1 = 0;
        int sum2 = 0;
        for (int i = 0; i < n-1; i++) {
            sum1 += a[i];
            sum2 += (i+1);
        }
        sum1 = sum1 + a[n-1];
        int result = sum1 - sum2;
        return result;
    }

用递归方式求一个整形数组的最大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class MaxNum {
    public static int max(int a,int b){
        return  (a>b) ? a: b;
    }
    public static int getMaxNum(int [] a,int begin){
        int n = a.length;
        if(1==n){
            return a[begin];
        }else{
            if (begin<=n-2)
                return max(a[begin],getMaxNum(a,begin+1));
            else
                return 0;
        }
    }
    public static void main(String[] args){
        int [] a = {0,16,2,3,4,5,10,7,8,9};
        System.out.println(getMaxNum(a,0));
    }
}

求一个数组数对之差的最大值（动态规划）

数组中的一个数字减去他右边子数组的中的一个数字可以得到一个差值，求所有可能的差值中的最大值。例如数组{1，4，17，3，2，9}中，最大差值为17-2=15。
方法一：蛮力法。双重循环遍历数组找到所有可能的差值然后找到差值中最大的值。
方法二：二分法。思想如下:把数组分为两个子数组，那么最大的差值只有3种可能
1.最大的差值对应的被减数和减数都在左子数组中，假设最大的差值为leftMax。
2.被减数和减数都在右子数组中，假设最大的差值为rightMax。
3.被减数是在左子数组中的最大值，减数是右子数组中的最小值，假设差值为mixMax。
那么由上文就可以知道最大的差值为这三个差值的最大值即max(leftMax,rightMax,mixMax)。
方法三：动态规划。思路如下：给以给定数组a,申请额外的数组diff和max，diff[i]是以数组中第i个数组为减数时，当前数组所有数对之差的最大值(也就是前i+1个数组成的子数组中最大的差值)，max[i]为前i+1个数的最大值。假设已经得到diff[i]，diff[i+1]的值有两种可能，diff[i]或者max[i]-diff[i]。由上面的所有分析可以得到的计算表达式diff[i+1]=max(diff[i],max[i-1]-a[i]); max[i+1]=max(max[i],a[i+1])

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
public class MaxSub {
    public static void main(String[] args){
        int [] a = {1,4,17,3,2,9};
        System.out.println(getMax(a));
    }
    public static int max(int m,int n){
        return m > n ? m : n;
    }
    private static int getMax(int[] a) {
        int n = a.length;
        if(a==null)
            return Integer.MIN_VALUE;
        if(n<=1)
            return Integer.MIN_VALUE;
        int[] diff = new int[n];
        int[] max = new int[n];
        diff[0] = 0;
        max[0] = 0;
        for (int i = 1; i < n ; i++) {
            diff[i] = max(diff[i-1],max[i-1] - a[i]);
            max[i] = max(max[i-1],a[i]);
        }
        return diff[n-1];
    }
}

上文还可以优化因为无需diff与max数组只是两个变量来保存前i+1个数的最大差值，和最大值即可。

求数组中绝对值最小的数

有一个升序排列的数组，数组中可能有正数、负数或者为0.求数组中元素的绝对值最小的数，例如，数组{-10，-5，-2，7，15，50}，绝对值最小的是-2。
绝对值最小可以分为三种情况考虑：
1.数组从第一个元素开始就是非负数，那么绝对值最小的数肯定是数组的第一个元素。
2.数组的最后一个元素为负数，那么绝对值最小的数一定是数组中的最后一个元素。
3.数组中既有整数又有负数，那么久需要找到正数与负数的分界点，如果分界点为0，那么0就是绝对值最小的数，如果分界点不为0，那么就要看分界点左右两个正负数的绝对值来比较大小了。
那么确定分界点最简单的方法就是顺序遍历数组，找出第一个非负数，时间复杂度最坏情况为O(n)。
二分法解决这个比较契合，主要思想如下：
1.取数组的中间位置的值a[mid]
2.如果a[mid]=0，那么这个数就是绝对值最小的值
3.a[mid]>0，如果a[mid-1]<0，那么就比较a[mid]与a[mid-1]的绝对值。如果a[mid-1]=0,那么它就是要找的数，否则在数组的左半部分继续查找（正负数的分界点在左半部分）。 4.a[mid]<0，如果a[mid+1]="">0,那么通过比较a[mid]与a[mid+1]就可以。如果a[mid+1]=0,那就是我们要找的值，否则接着在数组的右半部分继续查找（正负数的分界点在右半部分）。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
public class MinAbs {
    public static void main (String[] args){
        int a1[] = {-10,-5,-2,7,15,50};
        int a2[] = {2,4,6,8,27};
        int a3[] = {-13,-9,-7,-3};
        int value = getMinAbsValue(a1);
        System.out.println(value);
        value = getMinAbsValue(a2);
        System.out.println(value);
        value = getMinAbsValue(a3);
        System.out.println(value);
    }
    public static int min(int m,int n){
        return m < n ? m :n;
    }
    private static int getMinAbsValue(int[] a) {
        int n = a.length;
        //如果数组中没有负数
        if (a[0]>=0)
            return a[0];
        //数组中没有正数
        if (a[n-1]<=0)
            return a[n-1];
        int mid = 0;
        int begin = 0;
        int end = n-1;
        int abs_min = 0;
        //既有正数又有负数
        while(true){
            mid = begin + (end-begin)/2;
            //如果值等于0，直接返回
            if(a[mid]==0){
                return a[mid];
            }else if(a[mid]>0){
                //继续在数组左半部分找
                if(a[mid-1]>0)
                    end = mid -1;
                else if(a[mid-1]==0)
                    return 0;
                //找到正负数分界点
                else
                    break;
            }else{//如果值小于0在数组的右半部分查找
                //数组右半部分查找
                if(a[mid+1]<0)
                    begin = begin +1;
                else if(a[mid+1]==0)
                    return 0;
                //找到正负分界点
                else
                    break;
            }
        }
        //获取了正负分界点
        if(a[mid]>0){
            if(a[mid]<Math.abs(a[mid-1]))
                abs_min =a[mid];
            else
                abs_min = a[mid-1];
        }else {
            if (Math.abs(a[mid])<a[mid+1])
                abs_min = a[mid];
            else
                abs_min = a[mid+1];
        }
        return abs_min;
    }
}

求数组中两个元素的最小距离

给定一个数组，数组中包含有重复的元素，给出两个数n1,n2,求这两个数字在数组中所出现位置的最小距离，例如数组{4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8}中，4和8的最小距离为2。
实现思路如下：遍历数组，会遇到以下两种情况。
1.当遇到n1时候，记录下n1值对应的数组小标的位置n1_index，通过求n1_index与上次遍历n2的下标n2_index的差，可以求出最近一次遍历到的n1与n2的距离。
2.当遇到n2时候，记录下n2值对应的数组小标的位置n2_index，通过求n2_index与上次遍历n1的下标n1_index的差，可以求出最近一次遍历到的n1与n2的距离。
定义一个min_dist变量记录n1与n2的最小距离，在以上两种情况下，每次求出n1与n2的距离后与min_dist相比，求出最小值。这样只需要一次遍历就可以求出最小距离。时间复杂度为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
public class minDistancce {
    public static void main(String[] args){
        int a[] = {4,5,6,4,7,4,6,4,7,8,5,6,4,3,10,8};
        System.out.println(minDistancceNum(a,4,8));
    }
    public static int min (int a, int b){
        return a < b ? a : b;
    }
    private static int minDistancceNum(int[] a, int n1, int n2) {
        int n = a.length;
        int n1_index = -1;
        int n2_index = -1;
        int min_dist = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if(a[i]==n1){
                n1_index = i;
                if(n2_index > 0){
                    min_dist = min(Math.abs(min_dist),Math.abs(n1_index-n2_index));
                }
            }
            if(a[i]==n2){
                n2_index = i;
                if (n1_index>0){
                    min_dist = min(Math.abs(min_dist),Math.abs(n2_index-n1_index));
                }
            }
        }
        return min_dist;
    }
}

指定数字在数组中第一次出现的位置

给定数组a={3,4,5,6,5,6,7,8,9,8}，这个数组相邻元素之差都为1。给定数字9，他在数组中第一次出现的位置下标为8.
方法一：蛮力法 ，那么就是顺序遍历数组，和指定数字比较，如果两个数相等，那么返回下标。
方法二：跳跃搜索法 。例如需要查找9，数组相邻元素之差都为1，第一个元素为3，也就是元素9最早出现的位置是(9-3=6) 0+6=6(数组下标位置)，如果该位置不是，那么一定仍比9小，用相同的方法继续搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class FindIndex {
    public static void main(String[] args){
        int a[] = {3,4,5,6,5,6,7,8,9,8};
        System.out.println(findIndex(a,9));
    }
    private static int findIndex(int[] a, int t) {
        int n = a.length;
        int i = 0;
        while (i < n){
            if (t==a[i]){
                return i;
            }else {
                i = i + Math.abs(t-a[i]);
            }
        }
        return -1;
    }
}

对数组的两个子有序段进行合并

数组啊a[0,mid-1]和a[mid+1,n-1]是各自有序的，对数组a[0,n-1]的两个子有序段进行合并，得到a[0,n-1]整体有序。要求空间复杂度为O(1)。
假设数组a={1,5,6,7,9,2,4,8,10,13,14},mid=5,a[0]~a[4]是有序的，a[5]~a[10]是有序的，合并后的数组为{1,2,4,5,6,7,8,9,10,13,14},
由于限定空间复杂度为O(1)所以不能使用归并方法，最容易想到的就是插入排序方法。这种方法的时间复杂度为O(n^2),空间复杂度为O(1).
但是此种排序方法并没有用到条件数组a[0,mid-1],a[mid,n-1]都是各自有序的条件。所以有如下思路：
首先遍历数组中下标0~mid-1的元素，将遍历的元素的值与a[mid]比较，当遍历到ai时，
如果满足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],交换他们的位置。

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
public class TwoToOne {
    public static void main(String[] args){
        int a[] = {1,5,6,7,9,2,4,8,10,13,14};
        sort(a,5);
        for (int i = 0; i < a.length; i++) {
            System.out.print(a[i] + " ");
        }
    }
    private static void sort(int[] a, int mid) {
        int temp;
        for (int j = 0; j < mid-1; j++) {
            if(a[mid] < a[j]){
                temp = a[mid];
                a[mid] = a[j];
                a[j] = temp;
                findRightPlaceForMid(a,mid);
            }
        }
    }
    private static void findRightPlaceForMid(int[] a, int mid) {
        int n = a.length;
        int tmp;
        for (int i = mid; i < n-1; i++) {
            if(a[i+1]<a[i]){
                tmp = a[i+1];
                a[i+1] = a[i];
                a[i] = tmp;
            }
        }
    }
}

计算两个有序整型数组的交集

假设有两个含有n个元素的有序非降序的整型数组a和b，其中a={0,1,2,3,4},b={1,3,5,7,9}，那么他们的交集为{1,3}。
可以使用方法两路归并法。设两个数组分别为array1[n1]和array[n2]。分别以i,j从头开始遍历两个数组。在遍历的过程中若当前遍历位置的array1[i]与array2[j]相等，则此数为两个数组的交集，记录下来，并且继续向后遍历array1和array2，若array1[i]大于arrary2[j],
则继续向后遍历array2，若array1[i]小于array2[j],则需要继续向后遍历array1，知道一个数组结束遍历即停止。

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
public class FindMixed {
    public static void main(String[] args){
        int a[] = {0,1,2,3,4};
        int b[] = {1,3,5,7,9};
        ArrayList<Integer> mix = mixed(a,b);
        for (int i = 0; i < mix.size(); i++) {
            System.out.print(mix.get(i) + " ");
        }
    }
    private static ArrayList<Integer> mixed(int[] a, int[] b) {
        ArrayList<Integer> mix = new ArrayList<Integer>();
        int i=0,j=0;
        int n1 = a.length;
        int n2 = b.length;
        while (i<n1 && j<n2){
            if (a[i]==b[j]){
                mix.add(a[i]);
                i++;
                j++;
            }else if(a[i]>b[j]){
                j++;
            }else if(a[i]<b[j]){
                i++;
            }
        }
        return mix;
    }
}

判断一个数组中的数值是否连续相邻

一个数组序列，元素可能是0~65535中的任意一个数，相同的数值不会重复出现，0是例外，可以反复出现。从该数组中随意去除5个数判断这5个数是否相邻。需要注意一下几点。
1.5个数值允许是乱序的例如{8,7,5,0,6}
2.0可以通配任何数值例如{8,7,5,0,6}中的0可以通配成9或者4。
3.0可以多次出现。
4.全0算连续，只有一个非0算连续。
如果没有0的存在，要组成联系的数列，最大值和最小值的差值必须是4，存在0的情况下只要最大值和最小值的差值小于4就可以了，所以应该找出数列中非0的最大值和非0的最小值，时间复杂度O(n)如果非0最大-非0最小+1<<5,那么这5个数就是相邻的，否则不相邻。

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
public class FindContinuous {
    public static void main(String[] args){
        int a[] = {8,7,5,0,6};
        if(isContinuous(a)){
            System.out.print("连续");
        }else {
            System.out.print("不连续");
        }
    }
    private static boolean isContinuous(int[] a) {
        int n = a.length;
        int min = -1 ,max = -1;
        for (int i = 0; i < n; i++) {
            if(a[i]!=0){
                if (a[i]<min || min==-1)
                    min = a[i];
                if(a[i]>max || max==-1)
                    max = a[i];
            }
        }
        if(max-min>n-1)
            return false;
        else
            return true;
    }
}

如何求解数组中反序对的个数

给定一个数组a，如果a[i]>aj,那么a[i]与a[j]就称作为一个反序。例如给定数组{1，5，3，2，6}，共有(5，3)，(5，2)和(3，2)三个反序对。
方法一：蛮力法遍历数组元素，如果后面的数比前面的小，那么就是一个反序对。
方法二：分治归并法。相当于在归并排序的方法基础上额外使用一个计数器来记录反序对的个数。

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
public class MergeSort {
    public static int reverseCount = 0;
    public static void main(String[] args){
        int a[] = {1,5,3,2,6};
        merge_sort(a,0,a.length-1);
        System.out.println(reverseCount);
    }
    private static void merge_sort(int[] a, int begin, int end) {
        if (begin<end){
            int mid = (begin + end)/2;
            merge_sort(a,begin,mid);
            merge_sort(a,mid+1,end);
            merge(a,begin,mid,end);
        }
    }
    private static void merge(int[] a, int begin, int mid, int end) {
        int i,j,k,n1,n2;
        n1 = mid-begin + 1;
        n2 = end - mid;
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (i = 0,k=begin; i < n1; i++,k++) {
            L[i] = a[k];
        }
        for (i = 0,k=mid+1; i < n2; i++,k++) {
            R[i] = a[k];
        }
        for(k=begin,i=0,j=0;i<n1&&j<n2;k++){
            if(L[i]<R[j])
                a[k] = L[i++];
            else {
                reverseCount += mid - i + 1;
                a[k] = R[j++];
            }
        }
        if(i <n1){
            for(j=i;j<n1;j++,k++)
                a[k] = L[j];
        }
        if (j < n2){
            for (i=j;i<n2;i++,k++)
                a[k] = R[i];
        }
    }
}

如何求解最小三元组距离

已知3个升序整数数组啊a[l]、b[m]、c[n]。请在三个数组中各找一个元素，使得组成的三元组距离最小。三元组距离的定义：假设a[i]、b[j]和c[k]是一个三元组，那么距离Distance=max(|a[i]-b[j]|,|a[i]-c[k]|,|b[j]-c[k]|);
方法一：蛮力法三层循环分别遍历三个数组中的元素，分别求出他们的距离，然后在这些值里面找到最小值。
方法二：最小距离法。假设当前遍历到这三个数组中的元素分别为ai,bi，ci。并且ai<=bi=c[i]，此时他们的距离必定为D[i+1]=c[i+1]-a[i]，由于数组是升序的显然D[i+1]>=D[i]。因此D[i+1]不可能是最小距离。
2.如果接下来求ai,b[i+1],ci的距离，由于b[i+1]>=b[i]，如果b[i+1]<=c[i]，那么他们的距离仍为D[i+1]=ci-ai。如果b[i+1]>c[i]，此时D[i+1]=b[i+1]-a[i]，显然D[i+1]>=D[i],因此D[i+1]不可能是最小距离。
3.如果接下来求a[i+1]，b[i],c[i]的距离，如果a[i+1]<|c[i]-a[i]|+c[i]，此时他们建的距离为D[i+1]=c[i]-a[i+1]。显然D[i+1]<D[i]，因此D[i+1]可能是最小距离。
综上所述，只需要考虑第三种情况即可，思路如下：从3个数组的第一个元素开始，先求出他们的距离为minDist,接下来找出这三个数中最小数对应的数组，只对这个数组的下标往后移一个位置，接着求3个数组中当前元素的距离，若比minDist小，则把当前距离赋值给minDist，以此类推，直到遍历完其中一个数组。因为此种方法只需要对三个数字分别遍历一次，因此时间复杂度为O(l+m+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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
public class MinDistance {
    public static void main(String[] args){
        int a[] = {3,4,5,7};
        int b[] = {10,12,14,16,17};
        int c[] = {20,21,23,24,37,30};
        System.out.println(minDistancceNumber(a,b,c));
    }
    public static int min(int a,int b,int c){
        int min = a < b ? a : b;
        min = min < c ? min : c;
        return min;
    }
    public static int max(int a,int b,int c){
        int max = a > b ? a : b;
        max = max > c ? max : c;
        return max;
    }
    private static int minDistancceNumber(int[] a, int[] b, int[] c) {
        int aLen = a.length;
        int bLen = b.length;
        int cLen = c.length;
        int curDist = 0;
        int min = 0;
        int minDist = Integer.MAX_VALUE;
        int i=0;//数组a的下标
        int j=0;//数组b的下标
        int k=0;//数组c的下标
        while (true){
            curDist = max(Math.abs(a[i]-b[j]),Math.abs(a[i]-c[k]),Math.abs(b[j]-c[k]));
            if(curDist<minDist)
                minDist = curDist;
            //找到当前遍历的3个数组中的最小值
            min = min(a[i],b[j],c[k]);
            if (min==a[i]){
                if (++i>=aLen)
                    break;
            }else if(min==b[i]){
                if (++j>=bLen){
                    break;
                }
            }else {
                if (++k>=cLen)
                    break;
            }
        }
        return minDist;
    }
}
坚持原创技术分享，您的支持将鼓励我继续创作！