目录

数组

1、二维数组中的查找

2、旋转数组的最小数字

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

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

5、连续子数组的最大和

6、把数组排成最小的数

变形：把数组排成最大的数。

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

8、数组中只出现一次的数字

9、数组中重复的数字

10、构建乘积数组

---

数组

1、二维数组中的查找

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

思路一：

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        if array==[[]]:  #不能用not array，因为[[]]不为空，它是有一个元素为列表，但列表为空的数组
            return False
        x=len(array[0])-1
        y=len(array)-1
        #从左下角开始遍历
        startX=0
        startY=y
        #循环条件，到右上点结束，因为查找方向为向右或向上
        while startX<=x and startY>=0:
            if array[startX][startY]>target:
                startY-=1
            elif array[startX][startY]<target:
                startX+=1
            else:
                return True
        return False

思路二：

# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        rows=len(array)
        cols=len(array[0])
        for i in range(rows):
            for j in range(cols):
                if target==array[i][j]:
                    return True
        return False
if __name__=='__main__':
    answer=Solution()
    arr=[[1,2,3],[7,8,9],[11,12,13]]
    tar=9
    print(answer.Find(tar,arr))

2、旋转数组的最小数字

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

思路：最小值正好位于两段中间，用二分查找（折半查找法）即可。

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        start=0
        end=len(rotateArray)-1
        while start<end:
            mid=(start+end)//2
            #中间值<最左边值，由于本身是有两个递增数组组成，所以中间值右边的不需要考虑
            if rotateArray[mid]<rotateArray[start]:
                end=mid
            elif rotateArray[mid]>rotateArray[start]:
                start=mid
            else:
                return rotateArray[mid+1]

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

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

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self,array):
        if not array:
            return []
        odd=[]
        even=[]
        for i in array:
            if i%2==1:
                odd.append(i)
            else:
                even.append(i)
        return odd+even

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

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

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        lenth=len(numbers)
        a=set(numbers)
        for i in a:
            if numbers.count(i)>lenth/2:
               return i
        return 0

5、连续子数组的最大和

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

思路：

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self,array):
        if not array:
            return []
        sum_arr=0
        max_sum=array[0]
        for i in array:
            if sum_arr>0:
                sum_arr+=i
            else:
                sum_arr=i
            max_sum=max(sum_arr,max_sum)
        return max_sum

if __name__=='__main__':
    array=[1,-2,3,10,-4,7,2,-5]
    result=Solution()
    print(result.FindGreatestSumOfSubArray(array))

6、把数组排成最小的数

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

# -*- coding:utf-8 -*-
class Solution:
    def cmp(self,x,y):  #比较左+右，右+左，判断哪个小，然后返回
        s1=str(x)+str(y)
        s2=str(y)+str(x)
        if s1<=s2:
            return s1
        if s1>s2:
            return s2

    def PrintMinNumber(self,numbers):
        if not numbers:
            return ''
        numbers.sort()  #由小到大排序
        #不断替换index为0，1的值为cmp的返回值，直至最后数组中仅剩一个元素
        while len(numbers)>1:
            numbers[0]=self.cmp(numbers[0],numbers[1])
            numbers.remove(numbers[1])
        return numbers[0]

if __name__=='__main__':
    array=[3,32,321]
    result=Solution()
    print(result.PrintMinNumber(array))

变形：把数组排成最大的数。

class Solution:
    def cmp(self,x,y):  #比较左+右，右+左，判断哪个大，然后返回
        s1=str(x)+str(y)
        s2=str(y)+str(x)
        if s1<=s2:
            return s2
        if s1>s2:
            return s1

    def PrintMinNumber(self,numbers):
        if not numbers:
            return ''
        numbers.sort(reverse=True)  #由大到小排序
        #不断替换index为0，1的值为cmp的返回值，直至最后数组中仅剩一个元素
        while len(numbers)>1:
            numbers[0]=self.cmp(numbers[0],numbers[1])
            numbers.remove(numbers[1])
        return numbers[0]

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

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

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        count=0
        if not data or k not in data:
            return 0
        for i in data:
            if i==k:
                count+=1
        return count

8、数组中只出现一次的数字

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

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        number=[]
        for i in array:
            if i in number:
                number.remove(i)
            else:
                number.append(i)
        return number

9、数组中重复的数字

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

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

10、构建乘积数组

问题：给定一个数组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]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if not A:
            return []
        #计算左三角
        num=len(A)
        B=[None]*num
        B[0]=1
        for i in range(1,num):
            B[i]=B[i-1]*A[i-1]
        #计算右三角，自下而上
        #保留上次的计算结果乘本轮新的数，因为只是后半部分进行累加，所以设置一个temp，能够保留上次的结果
        temp=1
        for i in range(num-2,-1,-1): #从后往前遍历，不算最后一个（num-1），第一个for循环已经计算了
            temp*=A[i+1]
            B[i]*=temp
        return B

思路二：两层for循环，进行连乘，中间判断一下i != j即可。

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        n=len(A)
        B=[1]*n
        for i in range(n):
            for j in range(n):
                if i!=j:
                    B[i]*=A[j]
        return B

?

?

?

?

cs