数组

发表于 | 分类于 ， | 评论数：

二维数组中的查找

题目

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

思路

首先选取数组中右上角的数字。如果该数字等于要查找的数字，查找过程结束；如果该数字大于要查找的数组，剔除这个数字所在的列；如果该数字小于要查找的数字，剔除这个数字所在的行。也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除一行或者一列，这样每一步都可以缩小查找的范围，直到找到要查找的数字，或者查找范围为空。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows = len(array)
        if not rows:
            return False
        cols = len(array[0])
        if not cols:
            return False
        
        row = 0
        col = cols-1
        while row < rows and col >=0:
            if target == array[row][col]:
                return True
            elif target < array[row][col]:
                col -= 1
            else:
                row += 1
        return False

旋转数组的最小数字

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回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
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        if len(rotateArray) == 0:
            return 0
        left = 0
        right = len(rotateArray) - 1
        mid = 0
        while rotateArray[left] >= rotateArray[right]:
            # 二分结束标志
            if right - left == 1:
                mid = right
                break
            mid = left + (right - left) // 2
            # 特殊情况，如果二分位置的数据和左指针数据右指针数据都相等，此时无法进行判断，只能遍历查找最小值
            if rotateArray[left] == rotateArray[mid] and rotateArray[mid] == rotateArray[right]:
                return self.minInorder(rotateArray, left, right)
            # 如果二分位置数据大于等于左指针数据，更新左指针
            if rotateArray[mid] >= rotateArray[left]:
                left = mid
            # 反之更新右指针
            else:
                right = mid
        return rotateArray[mid]
    
    def minInorder(self, array, left, right):
        result = array[left]
        for i in range(left+1, right+1):
            if array[i] < result:
                result = array[i]
        return result

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

题目

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

思路

创建双向队列，遍历数组，奇数前插入，偶数后插入。最后使用assign方法实现不同容器但相容的类型赋值。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def reOrderArray2(self, array):
        # write code here
        res = []
        array_length = len(array)
        for i in range(array_length):
            if array[l-i-1] % 2 == 0:
                res.insert(0, array[-i-1])
            if array[i] % 2 == 0:
                res.insert(array[i])
        return res
    
    def reOrderArray(self, array):
        pos = 0
        for idx in range(len(array)):
            if array[idx] % 2:
                array.insert(pos, array.pop(idx))
                pos += 1   
        return array

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

题目

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

思路

数组中有一个数字出现的次数超过数组长度的一半，
也就是说它出现的次数比其他所有数字出现次数的和还要多。
因此我们可以考虑在遍历数组的时候保存两个值：一个是数组的一个数字，一个是次数。
当我们遍历到下一个数字的时候，如果下一个数字和我们之前保存的数字相同，则次数加1；
如果下一个数字和我们之前保存的数字不同，则次数减1。如果次数为零，我们需要保存下一个数字，
并把次数设为1。由于我们要找的数字出现的次数比其他所有数字出现的次数之和还要多，
那么要找的数字肯定是最后一次把次数设为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
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return 0
        
        # 找到最后一个将counter置为1的数字，如果有目标值，它最有可能
        maxTimesNumber = 0
        counter = 0
        for number in numbers:
            if counter == 0:
                maxTimesNumber = number
                counter = 1
            elif maxTimesNumber != number:
                counter -= 1
            elif maxTimesNumber == number:
                counter += 1
        timeCounter = 0
        for number in numbers:
            if number == maxTimesNumber:
                timeCounter += 1
                
        return maxTimesNumber if len(numbers)//timeCounter<2 else 0
        
        
        return maxTimesNumber

连续子数组的最大和

题目

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

思路

累加的子数组和，如果大于零，那么我们继续累加就行；否则，则需要剔除原来的累加和重新开始。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        if not array:
            return 0
        maxCount = array[0]
        curCount = array[0]
        
        for num in array[1:]:
            curCount += num
            if curCount > maxCount:
                maxCount = curCount
            if curCount <= 0:
                curCount = 0
        return maxCount

把数组排成最小的数

题目

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

思路

遇到这个题，全排列当然可以做，但是时间复杂度为O(n!)。在这里我们自己定义一个规则，对拼接后的字符串进行比较。

排序规则如下：

  • 若ab > ba 则 a 大于 b，
  • 若ab < ba 则 a 小于 b，
  • 若ab = ba 则 a 等于 b；

根据上述规则，我们需要先将数字转换成字符串再进行比较，因为需要串起来进行比较。比较完之后，按顺序输出即可。

代码

1
2
3
4
5
6
7
8
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if len(numbers) == 0:
            return ''
        compare = lambda a, b:cmp(str(a) + str(b), str(b) + str(a))
        min_string = sorted(numbers, cmp = compare)
        return ''.join(str(s) for s in min_string)

数组中的逆序对

题目

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

思路

思路1：

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

思路2：

归并排序的改进版，把数据分成前后两个数组(递归分到每个数组仅有一个数据项)。
合并数组，合并时，出现前面的数组值array[i]大于后面数组值array[j]时；
则前面数组array[i]~array[mid]都是大于array[j]的，count += mid+1 - 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
class Solution:
    def InversePairs(self, data):
        # write code here
        global cnt
        cnt = 0
        self.guibing(data)
        return cnt%1000000007
    
    def guibing(self,data):
        global cnt
        if len(data) == 1:
            return data
        mid = len(data)//2
        left = self.guibing(data[:mid])
        right = self.guibing(data[mid:])
        i = 0
        j = 0
        res = []
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                res.append(left[i])
                i += 1
            else:
                res.append(right[j])
                cnt += len(left) - i  #计算逆序对的数量
                j += 1
        res += left[i:]
        res += right[j:]
        return res

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

题目

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

思路

当然最好的方法是使用二分法先找到k的位置，在进行向前和向后遍历

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        i = 0
        for i in range(len(data)):
            if data[i] == k:
                break
        n = 0        
        for item in data[i:]:
            if item == k:
                n += 1
            else:
                break
        return n

数组中只出现一次的数字

题目

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

思路

我们可以将原始数组分成两个子数组，使得每个子数组包含一个只出现一次的数字，
而其他数字都成对出现。这样，我们就可以用上述方法找到那个孤苦伶仃的元素。

我们还是从头到尾一次异或数组中的每一个数字，那么最终得到的结果就是两个只出现一次的数组的异或结果。
因为其他数字都出现了两次，在异或中全部抵消了。由于两个数字肯定不一样，那么异或的结果肯定不为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。

代码

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
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        if len(array) < 2:
            return []
        
        resultExclusiveOR = 0
        # 将数组中的所有数字与或一遍，用来后面的分组条件
        for item in array:
            resultExclusiveOR ^= item
        
        # 找到与或结果出现第一个一的索引
        firstBitIs1 = self.FindFirstBitIsOne(resultExclusiveOR)
        
        # 遍历数组，分为两组数据进行相互与或，剩下的数字就是最终的两个数
        num1, num2 = 0, 0
        for item in array:
            if self.BitIsOne(firstBitIs1, item):
                num1 ^= item
            else:
                num2 ^= item
        return num1, num2
    
    def FindFirstBitIsOne(self, num):
        indexBit = 0
        while num & 1 == 0 and indexBit <= 32:
            indexBit += 1
            num = num >> 1
        return indexBit
        
    def BitIsOne(self, index, num):
        return (num >> index) & 1

数组中重复的数字

题目

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

思路

1.可以把当前序列当成是一个下标和下标对应值是相同的数组（时间复杂度为O(n),空间复杂度为O(1)）；
遍历数组，判断当前位的值和下标是否相等：
若相等，则遍历下一位；
2.若不等，则将当前位置i上的元素和a[i]位置上的元素比较：若它们相等，则找到了第一个相同的元素；
若不等，则将它们两交换。换完之后a[i]位置上的值和它的下标是对应的，
但i位置上的元素和下标并不一定对应；重复2的操作，直到当前位置i的值也为i，将i向后移一位，再重复2。

用数组的固定位置来存固定的数用来比较

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    # 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
    # 函数返回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        n = len(numbers)
        if n == 0:
            return False
        for i in range(n):
            if numbers[i] < 0 or numbers[i] > n-1:
                return False
        for i in range(n):
            while numbers[i] != i:
                if numbers[i] == numbers[numbers[i]]:
                    duplication[0] = numbers[i]
                    return True
                numbers[numbers[i]], numbers[i] = numbers[i], numbers[numbers[i]]
        return False

构建乘积的数组

题目

给定一个数组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[0] = A[1] * A[2] * … * A[n-1]，B[n-1] = A[0] * A[1] * … * A[n-2];）

思路

不断的将数组A第i 个数变成i

然后计算所有数的乘积

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def multiply(self, A):
        # write code here
        B = []
        if len(A) == 0:
            return B
        else:
            for i in range(len(A)):
                # 先将原本的数组A缓存
                tmp = A[i]
                # 将第i位换成1
                A[i] = 1
                # 通过reduce， 计算所有数据乘积
                B.append(reduce(lambda x,y:x*y, A))
                # 重置数据A
                A[i] = tmp
        return B
刘小恺(Kyle) wechat
如有疑问可联系博主