剑指offer题解 - 数组 | I'm Qiancun Huang

本系列为剑指offer刷题笔记，刷题平台为牛客网。

本文主要是数组相关题目题解总结。

1 二维数组中的查找

题目描述

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

解题思路

思路：由于数组是有序的，从左下角看，向上为递减，向右为递增，因此可以从左下角开始查找，当左下角元素比整数大时，上移，当左下角元素比整数小时，右移。

Python

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        if len(array) == 0:
            return False
        
        rows, cols = len(array), len(array[0])
        row, col = rows-1, 0
        
        while row >= 0 and col <= cols-1:
            if array[row][col] == target:
                return True
            elif array[row][col] > target:
                row -= 1
            else:
                col += 1
        
        return False

Java

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

6 旋转数组的最小数字

题目描述

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

解题思路

旋转之后的数组可以划分成两个有序的子数组，前面子数组的元素都大于后面子数组的元素，并且第一个元素大于最后一个元素最小的元素就是两个子数组的分界线使用二分查找，O(logn) 使用两个指针分别指向数组的第一个和最后一个元素

若中间元素小于它前一个元素，则中间元素为最小
若中间元素大于右边界，此时最小值位于中间元素之后（mid+1,r），左指针指向中间元素加1
若中间元素小于右边界，此时最小元素位于中间元素的前面(l, mid-1)，右指针指向中间元素减1.

Python

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        
        left, right = 0, len(rotateArray)-1
        
        while left <= right:
            mid = left + (right-left)//2
            if rotateArray[mid] < rotateArray[mid-1]:
                return rotateArray[mid]
            if rotateArray[mid] > rotateArray[right]:
                left = mid + 1
            else:
                right = mid - 1

Java

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
    if(array.length == 0)
        return 0;
    if(array.length == 1)
        return array[0];
    
    int left = 0;
    int right = array.length-1;
    while(left <= right)
    {
        int mid = (left+right)/2;
        if(array[mid] < array[mid-1])
            return array[mid];
        else if (array[mid] > array[right])
            left = mid + 1;
        else
            right = mid - 1;
    }
    return 0;
    }
}

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

题目描述

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

解题思路

对于不需要考虑奇数与奇数，偶数与偶数之间的相对位置不变的话，只需要设置左右两个指针，然后交换就行。但考虑相对位置不变的话最简单的方法就是新建两个数组。

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        if len(array) == 0 or len(array) == 1:
            return array
        
        odd, even = [], []
        for x in array:
            if x % 2 == 1:
                odd.append(x)
            else:
                even.append(x)
        return odd + even

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

题目描述

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

解题思路

思路1：使用hash函数，第一次遍历将每个数字出现次数保存下来，第二次遍历寻找次数超过数组长度一半的数字。

思路2：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if len(numbers) == 0:
            return 0
        
        Dict = {}
        for x in numbers:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
        
        for key, val in Dict.items():
            if val > len(numbers)//2:
                return key
        return 0

30 连续子数组的最大和

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

解题思路

思路：数组分析：下图是我们计算数组（1，-2，3，10，-4，7，2，-5）中子数组的最大和的过程。通过分析我们发现，累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if len(array) == 0:
            return 0
        
        maxsum = array[0]
        temp = 0
        for x in array:
            temp += x
            if temp > maxsum:
                maxsum = temp
            if temp < 0:
                temp = 0
        
        return maxsum

32 把数组排成最小的数

题目描述

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

解题思路

首先将数组中的数字全部转换为字符串存储在一个新的数组中，然后比较每两个数字串的拼接的mn和nm的大小，若mn<nm，则m更小，反之n更小，然后把更小的数放入一个新的List中，最后输出即可。使用冒泡排序很方便。

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if len(numbers) == 0:
            return ''
        if len(numbers) == 1:
            return str(numbers[0])
        
        numbers = [str(num) for num in numbers]
        
        for i in range(len(numbers)-1):
            for j in range(i+1, len(numbers)):
                if numbers[i]+numbers[j] > numbers[j] + numbers[i]:
                    numbers[i], numbers[j] = numbers[j], numbers[i]
        
        return ''.join(numbers)

35 数组中的逆序对

题目描述

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

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

数据范围：
    对于%50的数据,size<=10^4
    对于%75的数据,size<=10^5
    对于%100的数据,size<=2*10^5

示例1

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

解题思路

思路1：暴力解法，顺序扫描整个数组，每扫描到一个数字的时候，逐个比较该数字和它后面的数字的大小。如果后面的数字比它小，则这两个数字就组成一个逆序对。假设数组中含有n个数字，由于每个数字都要和O(n)个数字作比较，因此这个算法的时间复杂度是O(n^2)。

思路2：分治思想，采用归并排序的思路来处理，先分后治,如数组{7,5,6,4}，逆序对总共有5对，{7,5}，{7,6}，{7,4}，{5,4}，{6,4}；

先把数组分解成两个长度为2的子数组，再把这两个子数组分解成两个长度为1的子数组。接下来一边合并相邻的子数组，一边统计逆序对的数目。在第一对长度为1的子数组{7}、{5}中7>5，因此（7,5）组成一个逆序对。同样在第二对长度为1的子数组{6}，{4}中也有逆序对（6,4），由于已经统计了这两对子数组内部的逆序对，因此需要把这两对子数组进行排序，避免在之后的统计过程中重复统计。

逆序对的总数 = 左边数组中的逆序对的数量 + 右边数组中逆序对的数量 + 左右结合成新的顺序数组时中出现的逆序对的数量总结一下：这是一个归并排序的合并过程，主要是考虑合并两个有序序列时，计算逆序对数。对于两个升序序列。

设置两个下标：两个有序序列的首部。每次比较两个首部值，如果前首尾小于等于后首值，将较小值赋给辅助数组，第一个序列往前走一步，没有逆序对；否则，第二个序列值赋给辅助数组，第二个序列向前走一步，则有”第一个序列当前值及其后的长度“个逆序对；即最终要将两个有序序列合并到辅助数组并有序。这样，每次在合并前，先递归地处理左半段、右半段，则左、右半段有序，且左右半段的逆序对数可得到，再计算左右半段合并时逆序对的个数。

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        
        return self.Msort(data, 0, len(data)-1) %1000000007
    
    def Msort(self, data, left, right):
        if left >= right:
            return 0
        mid = left + (right-left) // 2
        l = self.Msort(data, left, mid)
        r = self.Msort(data, mid+1, right)
        return l + r + self.merge(data, left, mid, right)
    
    def merge(self, data, left, mid, right):
        res = 0
        i, j = left, mid+1
        temp = []
        while i <= mid and j <= right:
            if data[i] < data[j]:
                temp.append(data[i])
                i += 1
            else:
                res +=  (mid-i+1)
                temp.append(data[j])
                j += 1
                
        temp += data[i:mid+1] if i!=mid+1 else data[j:right+1]        
        
        data[left:right+1] = temp[:]
        
        return res

超时

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        
        if len(data) <= 1:
            return 0
        
        p = 0
        for i in range(len(data)-1):
            for j in range(i+1, len(data)):
                if data[i] > data[j]:
                    count += 1
        
        return p%1000000007

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code her
        if len(data)<=1:
            return 0
        # 思路1：运行超时
        # p = 0
        # for i in range(len(data)-1):
        #     for j in range(i+1,len(data)):
        #         if data[i] > data[j]:
        #             p += 1
        # return p % 1000000007
        # 思路2：归并排序
        temp = [x for x in data]
        return self.MSort(data,temp,0,len(data)-1)% 1000000007
    
    def MSort(self,data,temp,low,high):
        if low>=high:
            temp[low] = data[low]
            return 0
        mid = (low+high)//2
        left = self.MSort(temp,data,low,mid)
        right = self.MSort(temp,data,mid+1,high)
        count = 0
        i = low
        j = mid+1
        index = low
        while i <=mid and j <= high:
            if data[i]<=data[j]:
                temp[index] = data[i]
                i += 1
            else:
                temp[index] = data[j]
                j += 1
                count += mid-i+1
            index += 1
        while i <= mid:
            temp[index] = data[i]
            i += 1
            index += 1
        while j <= high:
            temp[index] = data[j]
            j += 1
            index += 1
        return count + left + right

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code her
        if len(data) <= 1:
            return 0
        # 思路1：运行超时
        # p = 0
        # for i in range(len(data)-1):
        #     for j in range(i+1,len(data)):
        #         if data[i] > data[j]:
        #             p += 1
        # return p % 1000000007
        # 思路2：归并排序
        temp = [x for x in data]
        return self.MSort(data, temp, 0, len(data) - 1) % 1000000007

    def MSort(self, data, temp, low, high):
        if low >= high:
            temp[low] = data[low]
            return 0
        mid = (low + high) // 2
        left = self.MSort(temp, data, low, mid)
        right = self.MSort(temp, data, mid + 1, high)
        return left + right + self.merge(data, temp, low, mid, high)

    def merge(self, data, temp, low, mid, high):
        count = 0
        i = low
        j = mid + 1
        index = low
        while i <= mid and j <= high:
            if data[i] <= data[j]:
                temp[index] = data[i]
                i += 1
            else:
                temp[index] = data[j]
                j += 1
                count += mid - i + 1
            index += 1
        while i <= mid:
            temp[index] = data[i]
            i += 1
            index += 1
        while j <= high:
            temp[index] = data[j]
            j += 1
            index += 1
        return count

37 数字在排序数组中出现的次数

题目描述

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

解题思路

使用二分搜索，当搜索到与关键字相等时，在上下限之间遍历，计数。没找到则返回0

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        
        if len(data) == 0:
            return 0
        left, right = 0, len(data)-1
        while left <= right:
            mid = (left+right)//2
            if data[mid] == k:
                count = 0
                for i in range(left, right+1):
                    if data[i] == k:
                        count += 1
                return count
            elif data[mid] > k:
                right = mid-1
            else:
                left = mid+1
        return 0

40数组中只出现一次的数字

题目描述

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

解题思路

思路1：考虑用哈希表的方法，但是空间复杂度不是O（1）。应该怎么做才能即满足时间复杂度是O（n）又满足空间复杂度是O（1）的要求呢？

思路2：我们可以想一想“异或”运算的一个性质，我们直接举例说明。

举例：{2,4,3,6,3,2,5,5}

这个数组中只出现一次的两个数分别是4和6。怎么找到这个两个数字呢？

我们先不看找到俩个的情况，先看这样一个问题，如何在一个数组中找到一个只出现一次的数字呢？比如数组：{4,5,5}，唯一一个只出现一次的数字是4。

我们知道异或的一个性质是：任何一个数字异或它自己都等于0。也就是说，如果我们从头到尾依次异或数组中的每一个数字，那么最终的结果刚好是那个只出现一次的数字。比如数组{4,5,5}，我们先用数组中的第一个元素4（二进制形式：0100）和数组中的第二个元素5（二进制形式：0101）进行异或操作，0100和0101异或得到0001，用这个得到的元素与数组中的三个元素5（二进制形式：0101）进行异或操作，0001和0101异或得到0100，正好是结果数字4。这是因为数组中相同的元素异或是为0的，因此就只剩下那个不成对的孤苦伶仃元素。

现在好了，我们已经知道了如何找到一个数组中找到一个只出现一次的数字，那么我们如何在一个数组中找到两个只出现一次的数字呢？如果，我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。

我们还是从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为0，也就是说这个结果数组的二进制表示至少有一个位为1。我们在结果数组中找到第一个为1的位的位置，记为第n位。现在我们以第n位是不是1为标准把元数组中的数字分成两个子数组，第一个子数组中每个数字的第n位都是1，而第二个子数组中每个数字的第n位都是0。

举例：{2,4,3,6,3,2,5,5}

我们依次对数组中的每个数字做异或运行之后，得到的结果用二进制表示是0010。异或得到结果中的倒数第二位是1，于是我们根据数字的倒数第二位是不是1分为两个子数组。第一个子数组{2,3,6,3,2}中所有数字的倒数第二位都是1，而第二个子数组{4,5,5}中所有数字的倒数第二位都是0。接下来只要分别两个子数组求异或，就能找到第一个子数组中只出现一次的数字是6，而第二个子数组中只出现一次的数字是4。

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        
        Dict = {}
        for x in array:
            if x not in Dict:
                Dict[x] = 1
            else:
                Dict[x] += 1
        
        res = []
        for key, val in Dict.items():
            if val == 1:
                res.append(key)
        
        return res

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        
        num = 0
        for x in array:
            num ^= x
        index = self.getfitstBitIs1(num)
        num1, num2 = 0, 0
        for x in array:
            if self.BitIs1(x, index):
                num1 ^= x
            else:
                num2 ^= x
        return num1, num2
    
    def getfitstBitIs1(self, num):
        index = 0
        while num&1 == 0 and index <= 32:
            index += 1
            num = num>>1
        return index
    
    def BitIs1(self, num, index):
        num =  num >> index
        return num & 1

50数组中重复的数字

题目描述

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

思路1：建立一个哈希表，这样实在O(n)的时间查找到，但是空间复杂度O(n)

思路2：还可以把当前序列当成是一个下标和下标对应值是相同的数组（时间复杂度为O(n),空间复杂度为O(1)）；遍历数组，判断当前位的值和下标是否相等：

若相等，则遍历下一位；若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则找到了第一个相同的元素；若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，但i位置上的元素和下标并不一定对应；重复2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2。如果还是不懂，看下面的实例分析就懂了！

举例说明：{2,3,1,0,2,5,3}

0(索引值)和2(索引值位置的元素)不相等，并且2(索引值位置的元素)和1(以该索引值位置的元素2为索引值的位置的元素)不相等，则交换位置，数组变为：{1,3,2,0,2,5,3}；
0(索引值)和1(索引值位置的元素)仍然不相等，并且1(索引值位置的元素)和3(以该索引值位置的元素1为索引值的位置的元素)不相等，则交换位置，数组变为：{3,1,2,0,2,5,3}；
0(索引值)和3(索引值位置的元素)仍然不相等，并且3(索引值位置的元素)和0(以该索引值位置的元素3为索引值的位置的元素)不相等，则交换位置，数组变为：{0,1,2,3,2,5,3}；
0(索引值)和0(索引值位置的元素)相等，遍历下一个元素；
1(索引值)和1(索引值位置的元素)相等，遍历下一个元素；
2(索引值)和2(索引值位置的元素)相等，遍历下一个元素；
3(索引值)和3(索引值位置的元素)相等，遍历下一个元素； 4(索引值)和2(索引值位置的元素)不相等,但是2(索引值位置的元素)和2(以该索引值位置的元素2为索引值的位置的元素)相等，则找到了第一个重复的元素。

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if len(numbers) <= 1:
            return False
        
        seen = []
        for x in numbers:
            if x not in seen:
                seen.append(x)
            else:
                duplication[0] = x
                return True
        
        return False

# -*- coding:utf-8 -*-
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        if len(numbers) <= 1:
            return False

    
        for i in range(len(numbers)):
            while i != numbers[i]:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                else:
                    numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]
                
        return False

51构建乘积数组

题目描述

给定一个数组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]。不能使用除法。

解题思路

观察下公式，你会发现，B[i]公式中没有A[i]项，也就是说如果可以使用除法，就可以用公式B[i]=A[0]A[1]…..A[n-1]/A[i]来计算B[i]，但是题目要求不能使用，因此我们只能另想办法。

可以把B[i]=A[0]A[1]…..A[i-1]A[i+1]…..A[n-1]。看成A[0]A[1]…..A[i-1]和A[i+1]…..A[n-2]A[n-1]两部分的乘积。即通过A[i]项将B[i]分为两部分的乘积。效果如下图所示：

不妨设定C[i]=A[0]A[1]…A[i-1]，D[i]=A[i+1]…A[n-2]A[n-1]。C[i]可以用自上而下的顺序计算出来，即C[i]=C[i-1]A[i-1]。类似的，D[i]可以用自下而上的顺序计算出来，即D[i]=D[i+1]A[i+1]。如果还是不明白，没有关系，直接看下代码，细细体会下就懂了。

第一个for循环用来计算上图1范围的数，第二个for循环用来计算上图2范围的数。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if len(A) <= 1:
            return False
        
        B = [1] * len(A)
        for i in range(1, len(A)):
            B[i] = B[i-1]*A[i-1]
        
        temp = 1
        for i in range(len(A)-2,-1, -1):
            temp *= A[i+1]
            B[i] *= temp
        
        return B