剑指offer刷题总结(四)数组

1. 数组中重复的数字

题目描述：

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2

思路：

从头到尾依次扫描这个数组中的每个数字。当扫描到下标为i的数字时，首先比较这个数字(用m表示)是不是等于i。如果是，接着扫描下一一个数字。如果不是，再拿它和第m个数字进行比较。如果它和第m个数字相等，就找到了-个重复的数字(该数字在下标为i和m的位置都出现了)。如果它和第m个数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再重复这个比较、交换的过程，直到我们发现一个重复的数字。
以数组{2, 3, 1,0,2, 5, 3}为例来分析找到重复数字的步骤。数组的第0个数字(从0开始计数，和数组的下标保持一致)是2,与它的下标不相等，于是把它和下标为2的数字1交换。交换之后的数组是{1,3,2, 0,2,5,3}。、此时第0个数字是1,仍然与它的下标不相等，继续把它和下标为1的数字3交换，得到数组{3, 1,2,0,2,5,3}。接下来继续交换第0个数字3和第3个数字0，得到数组{0，1,2, 3,2,5,3}。此时第0数字的数值为0，接着扫描下一个数字。在接下来的几个数字中，下标为1、2、3的三个数字分别为1、2、3,它们的下标和数值都分别相等，因此不需要做任何操作。接下来扫描到下标为4的数字2。由于它的数值与它的下标不相等，再比较它和下标为2的数字。注意到此时数组中下标为2的数字也是2,也就是数字2在下标为2和下标为4的两个位置都出现了，因此找到一个重复的数字。

代码实现：

/**
 * @ClassName problem1
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 14:02
 * Version 1.0
 **/
public class problem1 {

    /**
     * 用hashmap存放数组
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers==null||numbers.length==0) {
            duplication[0] = -1;
            return false;
        }
        HashMap<Integer,Integer> hashMap=new HashMap<>();
        for(int number:numbers){
            if(hashMap.containsKey(number)){
                duplication[0]=number;
                return true;
            }
            hashMap.put(number,1);
        }
        duplication[0]=-1;
        return false;
    }

    /**
     * 比较好的解决方式,时间复杂度O(n),空间复杂度O(1)
     * 数组中的数字为0到n-1的范围内。
     * 如果这个数组中没有重复的数字，则对应的i位置的数据也为i。可以重排此数组
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate2(int numbers[],int length,int [] duplication) {
        if(numbers==null||numbers.length==0) {
            duplication[0] = -1;
            return false;
        }
        for(int i=0;i<numbers.length;i++){
            while(numbers[i]!=i){
                if(numbers[numbers[i]]==numbers[i]){
                    duplication[0]=numbers[i];
                    return true;
                }
                int temp=numbers[numbers[i]];
                numbers[numbers[i]]=numbers[i];
                numbers[i]=temp;
            }
        }
        duplication[0] = -1;
        return false;
    }


    /**
     * 先排序
     * @param numbers
     * @param length
     * @param duplication
     * @return
     */
    public boolean duplicate3(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length ==0) {
            duplication[0] = -1;
            return false;
        }
        Arrays.sort(numbers);
        for (int i = 0; i < length -1; i++) {//注意这个i的范围可能越界
            if(numbers[i] == numbers[i+1]) {
                duplication[0] = numbers[i];
                return true;
            }
        }
        return false;

    }
}

2. 构建乘积数组

题目描述：

给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素$B[i]=A[0]A[1]…A[i-1]*A[i+1]…*A[n-1]$。不能使用除法。

思路：
用矩阵的方式，先计算左下三角，再计算右上三角。根据图来分析即可。

代码实现：

package Arr;

/**
 * @ClassName problem2
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 14:47
 * Version 1.0
 **/
public class problem2 {

    public int[] multiply(int[] A) {
        if(A==null||A.length==0)
            return A;
        int[] B=new int[A.length];
        B[0]=1;
        for(int i=1;i<B.length;i++){
            B[i]=B[i-1]*A[i-1];
        }
        int temp=1;
        for(int i=B.length-1;i>=0;i--){
            B[i]*=temp;
            temp*=A[i];
        }
        return B;
    }
}

3. 二维数组的查找

题目描述:

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

思路：

利用二维数组由上到下，由左到右递增的规律，那么选取右上角的元素a[row] [col]与target进行比较，
当target小于元素a[row] [col]时，那么target必定在元素a所在行的左边,即col–；
当target大于元素a[row][col]时，那么target必定在元素a所在列的下边,即row++；

代码实现：

package Arr;

/**
 * @ClassName problem3
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 15:12
 * Version 1.0
 **/
public class problem3 {

    public boolean Find(int target, int [][] array) {
        int row = 0;
        int col = array[0].length -1;
        while(row<array.length && col>= 0) {
            if (array[row][col]==target) {
                return true;
            }
            else if (array[row][col]<target) {
                row++;
            }
            else {
                col--;
            }
        }
        return false;

    }
}

4. 数组中只出现一次的数字

题目描述：

一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：

当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，最后剩下的就是落单的数，因为成对儿出现的都抵消了。

依照这个思路，我们来看两个数（我们假设是AB）出现一次的数组。我们首先还是先异或，剩下的数字肯定是A、B异或的结果，这个结果的二进制中的1，表现的是A和B的不同的位。我们就取第一个1所在的位数，假设是第3位，接着把原数组分成两组，分组标准是第3位是否为1。如此，相同的数肯定在一个组，因为相同数字所有位都相同，而不同的数，肯定不在一组。然后把这两个组按照最开始的思路，依次异或，剩余的两个结果就是这两个只出现一次的数字。

所以，只于k位上是1的异或，就把其中一组的落单的那个异或出来了。此外a^b=d 则a^d=b满足结果的互换。知道异或的结果和其中一个，可以求得另一个。

代码实现：

/**
 * @ClassName problem4
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 16:14
 * Version 1.0
 **/
public class problem4 {

    public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
        int eO = 0,eOne = 0;
        for(int num:array)
            eO ^=num;
        int firstOne = eO &(~eO +1);//求得二进制中第一位1，比如101和011得到010
        for(int cur:array)
            if ((cur&firstOne) !=0) {//把第k位是1的一组找出来进行异或
                eOne ^=cur;
            }//最终结果就是第k位是1且落单的那个
        num1[0] = eOne;
        num2[0] = eOne^eO;//异或结果的运算规则。
    }

}

5. 和为S的两个数

题目描述：

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

代码实现：

/**
 * @ClassName problem5
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 16:33
 * Version 1.0
 **/
public class problem5 {
    /**
     * 若a[low] + a[high] == sum，就是答案（和一定，两个数字相差越远乘积越小）
     * 若a[low] + a[high] > sum，aj肯定不是答案之一，high -= 1
     * 若a[low] + a[high] < sum，ai肯定不是答案之一，low += 1
     * @param array
     * @param sum
     * @return
     */
    public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
        int low=0;
        int high=array.length;
        ArrayList<Integer> arrayList=new ArrayList<>();

        while(low<high){
            if(array[low]+array[high]<sum){
                low++;
            }else if(array[low]+array[high]>sum){
                high--;
            }else{
                arrayList.add(array[low]);
                arrayList.add(array[high]);
                break;
            }

        }
        return arrayList;
    }
}

6. 和为S的连续正数序列

题目描述：

小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列?

代码实现：

package Arr;

import java.util.ArrayList;

/**
 * @ClassName problem6
 * @Description TODO
 * @Author niran
 * @Date 2019/8/3 16:52
 * Version 1.0
 **/
public class problem6 {
    public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> resList = new ArrayList<>();
        for(int low = 1;low<=sum;low++) {
            for(int high=sum;high>low;high--){
                int result = 0;
                for (int i = low; i <= high; i++) {
                    result += i;
                }
                if(result==sum) {
                    ArrayList<Integer> arrayList = new ArrayList<>();
                    for (int i = low; i <= high; i++) {
                        arrayList.add(i);
                    }
                    resList.add(arrayList);
                    break;
                }
            }
        }
        return resList;
    }
}

解法二：

/**
 * @ClassName problem6
 * @Description TODO  和为S的连续正数序列
 * @Author niran
 * @Date 2019/8/3 16:52
 * Version 1.0
 **/
public class problem6 {
    /*
     *初始化small=1，big=2;
     *small到big序列和小于sum，big++;大于sum，small++;
     *当small增加到(1+sum)/2是停止
     */
    public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        if(sum < 3) //不重复，最少有两个数字
            return res;
        int small = 1;
        int big = 2;
        //因为是两个数，假设small是这个
        //，big假设也是这个，和为sum+1，所以到此就可以停了，后面肯定更大
        while(small !=(sum+1)/2) {
            int cursum = SumOfList(small, big);
            if(cursum == sum) {
                for (int i = small; i <= big; i++) {
                    list.add(i);
                }
                res.add(new ArrayList<>(list));
                list.clear();//清理掉
                big++;//找到一组，继续big++，找下一组满足要求的。
            }
            else if (cursum > sum) {
                small++;
            }
            else {
                big++;
            }
        }
        return res;
    }
    //计算list内的数据的和
    public int SumOfList(int small, int big) {
        int sum = 0;
        for (int i = small; i <= big; i++) {
            sum +=i;
        }
        return sum;
    }
}

7. 调整数组顺序使奇数位于偶数前面

题目描述：

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

代码实现：

/**
 * @ClassName problem7
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 8:53
 * Version 1.0
 **/
public class problem7 {

    public void reOrderArray(int [] array) {
        List<Integer> JList =new ArrayList<>();
        List<Integer> OList =new ArrayList<>();
        for(int a:array){
            if(a%2==0)
                OList.add(a);
            else
                JList.add(a);
        }
        JList.addAll(OList);
        for(int i=0;i<array.length;i++){
            array[i]=JList.get(i);
        }

    }
    //前一种方法的执行时间低，但是需要额外的空间，后一种方法执行时间高一点，但是不需要额外的空间
    public void reOrderArray2(int[] array) {
        int temp = 0;
        for (int i = 0; i < array.length - 1; i++) {
            for (int j = 0; j < array.length - 1 - i; j++) {
                // 前偶后奇数就交换
                if ((array[j] & 1) == 0 && (array[j + 1] & 1) == 1) {  //与1位与得1就是奇数，1只有最后一位是1
                    temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }
}

8. 数组中出现次数超过一半的数字

题目描述

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

代码实现：

/**
 * @ClassName problem8
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 9:22
 * Version 1.0
 **/
public class problem8 {

    /**
     * 用哈希表记录次数
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer,Integer> map=new HashMap<>();
        for(int a:array){
            if(map.containsKey(a)){
                map.put(a,map.get(a)+1);
            }else{
                map.put(a,1);
            }
        }

        for(int a:array){
            if(map.get(a)>array.length/2){
                return a;
            }
        }
        return 0;
    }

    /**
     * 先排序取中间的数再验证
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution2(int [] array) {
        Arrays.sort(array);
        int count=0;
        for(int a:array){
            if(a==array[array.length/2])
                count++;

        }
        return count>array.length/2?array[array.length/2]:0;
    }

    /**
     * 一次再数组中删除两个不同的数，最后剩下的数   有可能    是超过一半的。所以要检验一下。 一个数出现次数大于一半，他肯定会被剩下来，但是剩下来的缺不一定满足。
     * 算法步骤：
     * 如果times为0，就把候选设为当前值。
     * 如果下个数和候选一样，times就++。
     * 如果下个数和候选不一样，times就--。相当于对子，同归于尽。因为超过一半的数肯定超过剩下的所有数。所以和这个数对，这个数肯定会剩下来。
     * 但是剩下的数不一定是，比如 1 2 3 剩下3 比如 1 2 1 3 3 3 2 2 也是剩下3.所以要余外的判断，看是否这个数真的超过。
     * @param array
     * @return
     */
    public int MoreThanHalfNum_Solution3(int [] array) {
        int cand = 0;
        int times = 0;
        for (int i = 0; i < array.length; i++) {
            if (times == 0) {
                cand = array[i];
                times = 1;
            } else if (array[i] == cand) {
                times++;
            } else {
                times--;
            }
        }
        int count=0;
        for(int a:array){
            if(a==cand)
                count++;

        }
        return count>array.length/2?cand:0;
    }
}

9. 连续子数组的最大和

题目描述:

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

代码实现：

/**
 * @ClassName problem9
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 10:00
 * Version 1.0
 **/
public class problem9 {
    /**
     * 不是看当前的值，而是看当前的累计值，如果加上当前的值累计值为负
     * 就继续从下一个数开始累计，如果为正，那就继续加，
     * 但是要时刻保存下最大值来，因为后面的累计有可能小。
     * @param array
	 * @return
     **/
    public int FindGreatestSumOfSubArray(int[] array) {
        int maxSum=array[0];
        int Sum=0;
        for(int i=0;i<array.length;i++) {
            Sum+=array[i];
            if (Sum > maxSum) {
                maxSum = Sum;
            }
            if (Sum <0) {
                Sum=0;
            }
        }
        return maxSum;
    }
}

10. 把数组排成最小的数

题目描述:

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路：
考虑到大数问题，先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。 排序规则如下： 若ab > ba 则 a > b， 若ab < ba 则 a < b， 若ab = ba 则 a = b；

代码实现：

/**
 * @ClassName problem10
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 10:50
 * Version 1.0
 **/
public class problem10 {
    /**
     * 主要就是规则的制定，将两个数字转换为字符串，防止溢出
     * 假设两个数字m和n，拼接有mn和nm
     * 如果mn>nm, 我们打印nm，此时定义n小于m。（此处小于是我们定义的）
     * 不是m和n的大小关系，
     * 而是看拼了之后的大小，来决定m和n的大小。
     * 如果mn<nm 那么就是m小于n。
     * @param numbers
     * @return
     */
    public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0)
            return "";
        int len = numbers.length;
        String[] str = new String[len];
        StringBuffer sb = new StringBuffer();
        //将数字型的放在字符串数组中。
        for (int i = 0; i < len; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        //根据规则排好序，将结果依次放入stringbuffer中就行了
        Arrays.sort(str, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String s1=o1+o2;
                String s2=o2+o1;
                return s1.compareTo(s2);
            }
        });
        for (int i = 0; i < len; i++) {
            sb.append(str[i]);
        }
        return sb.toString();
    }
}

11. 数组中的逆序对

题目描述:
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。 即输出P%1000000007

输入描述:
题目保证输入的数组中没有的相同的数字

示例1

输入1,2,3,4,5,6,7,0
输出7

代码实现：

/**
 * @ClassName problem11
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 11:41
 * Version 1.0
 **/
public class problem11 {
    int count = 0;
    public int InversePairs(int [] array) {
        if(array == null || array.length ==0)
            return 0;
        mergeSort(array, 0, array.length -1);
        return count;

    }
    public void mergeSort(int []array, int start, int end) {
        if(start < end) {
            int mid = (start + end)/2;
            mergeSort(array, start, mid);
            mergeSort(array, mid + 1, end);
            merge(array, start, mid, mid+ 1, end);
        }
    }
    public void merge(int []array,int start1,int end1, int start2, int end2) {
        int i = end1;
        int j = end2;
        int k = end2 - start1 ;
        int [] temp = new int[end2- start1 +1];
        while(i >= start1 && j >=start2) {
            if(array[i] > array[j]) {
                //假设此时两个归并的是17 19 22 || 16 18 21
                //那么22大于21，所以可以看出对应22
                //有三个，22 16 22 18 22 21
                temp[k--] = array[i--];
                count = count + j - start2 +1;
                count %= 1000000007;
            }
            else
                temp[k--] = array[j--];
        }
        while(i >= start1)
            temp[k--] = array[i--];
        while(j >= start2)
            temp[k--] = array[j--];

        int m = start1;
        for(int element:temp)
            array[m++] = element;

    }

}

12. 数字在排序数组中出现的次数

题目描述：

统计一个数字在排序数组中出现的次数。

代码实现：

/**
 * @ClassName problem12
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 11:43
 * Version 1.0
 **/
public class problem12 {

    /**
     * 方法一
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK(int[] array, int k) {
        int count = 0;
        for (int a : array) {
            if (a == k)
                count++;
        }
        return count;
    }


    /**
     * 方法二
     * 通过二分法查找K的起始位置和终止位置
     * @param array
     * @param k
     * @return
     */
    public int GetNumberOfK2(int[] array, int k) {
        int firstK=getFirstK(array,k,0,array.length-1);
        int lastK=getLastK(array,k,0,array.length-1);
        if(firstK<=lastK&&lastK!=-1){
            return lastK-firstK+1;
        }
        return 0;
    }


    /**
     * 二分法查找起始位置
     * @param array
     * @param k
     * @param start
     * @param end
     * @return
     */
    public int getFirstK(int[] array, int k, int start, int end) {
        if(start > end)
            return -1;
        int mid = (start + end) / 2;

        if (k < array[mid]) {
            end = mid - 1;
            return getFirstK(array, k, start, end);
        } else if (k > array[mid]) {
            start = mid + 1;
            return getFirstK(array, k, start, end);
        } else {
            int i = mid;
            while (i > 0 && array[i - 1] == k) {
                i--;
            }
            return i;
        }
    }
    /**
     * 二分法查找终止位置
     * @param array
     * @param k
     * @param start
     * @param end
     * @return
     */
    public int getLastK(int[] array, int k, int start, int end) {
        if(start > end)
            return -1;
        int mid = (start + end) / 2;

        if (k < array[mid]) {
            end = mid - 1;
            return getFirstK(array, k, start, end);
        } else if (k > array[mid]) {
            start = mid + 1;
            return getFirstK(array, k, start, end);
        } else {
            int i = mid;
            while (i<array.length&& array[i] == k) {
                i++;
            }
            return i-1;
        }
    }
}

13. 旋转数组的最小数字

题目描述：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：
利用二分法，找到中间的数，然后和最左边的值进行比较，若大于最左边的数，则最左边从mid开始，若小于最右边值，则最右边从mid开始。若左中右三值相等，则取mid前后值中较小的数。

代码实现：

/**
 * @ClassName problem13
 * @Description TODO
 * @Author niran
 * @Date 2019/8/4 14:46
 * Version 1.0
 **/
public class problem13 {

    /**
     * 二分法
     * @param array
     * @return
     */
    public int minNumberInRotateArray(int [] array) {
        int start=0;
        int end=array.length-1;
        int mid;
        while(start<=end){
            mid=(start+end)/2;
            if(array[start]<=array[mid]){
                start=mid;
            }else{
                end=mid;
            }
        }
        return array[end];
    }

    /**
     * 遍历法
     * @param array
     * @return
     */
    public int minNumberInRotateArray2(int [] array) {
        for(int i=1;i<array.length;i++){
            if(array[i]<array[i-1])
                return array[i];
        }
        return 0;
    }
}