劍指offer | 數組問題彙總

數組問題彙總

• 1 前言
• 2 題目
• • 2.1 調整數組順序使奇數位于偶數前面
  • • 2.1.1 思路1
    • 2.1.2 代碼1
    • 2.1.3 思路2
    • 2.1.4 代碼2
  • 2.2 數組中出現次數超過一半的數字
  • • 2.2.1 思路1
    • 2.2.2 代碼1
    • 2.2.3 思路2
    • 2.2.4 代碼2
  • 2.3 連續子數組的最大和
  • • 2.3.1 思路1
    • 2.3.2 代碼1
    • 2.3.3 思路2
    • 2.3.4 代碼2
  • 2.4 把數組排成最小的數
  • • 2.4.1 思路
    • 2.4.2 代碼
  • 2.5 數組中的逆序對
  • • 2.5.1 題目
    • 2.5.2 思路1
    • 2.5.3 代碼1
    • 2.5.4 思路2
    • 2.5.5 代碼2
  • 2.6 數字在排序數組中出現的次數
  • • 2.6.1 題目
    • 2.6.2 思路1
    • 2.6.3 代碼1
    • 2.6.4 思路2
    • 2.6.5 代碼2
  • 2.7 數組中隻出現一次的數字
  • • 2.7.1 題目
    • 2.7.2 思路1
    • 2.7.3 代碼1
    • 2.7.4 思路2
  • 2.8 數組中重複的數字
  • • 2.8.1 題目
    • 2.8.2 思路1
    • 2.8.3 代碼1
  • 2.9 建構乘積數組
  • 2.9.1 題目描述
  • 2.9.2 思路1
  • 2.9.3 代碼1
• 3 參考

1 前言

2 題目

2.1 調整數組順序使奇數位于偶數前面

輸入一個整數數組，實作一個函數來調整該數組中數字的順序，使得所有的奇數位于數組的前半部分，所有的偶數位于數組的後半部分，并保證奇數和奇數，偶數和偶數之間的相對位置不變。

2.1.1 思路1

思路：

• 周遊所有元素 然後用兩個空list分别存取奇數和偶數！
• 最後拼接兩個list 奇數在前面！

2.1.2 代碼1

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        alist = [] # 存取奇數
        blist = [] # 存取偶數
        for i in array:
            if i%2 == 0:
                # 表明為偶數
                blist.append(i)
            else:
                # 表明為奇數
                alist.append(i)
        return alist + blist
           

2.1.3 思路2

隻用一個list實作！

• 即遇到奇數在list前面插入insert
• 遇到偶數在list後面append

2.1.4 代碼2

# -*- coding:utf-8 -*-
class Solution:
    def reOrderArray(self, array):
        # write code here
        res = []
        l = len(array)
        for i in range(l):
            if array[l-i-1] % 2 != 0:
                res.insert(0,array[-i-1])
            if array[i] % 2 == 0:
                res.append(array[i])
        return res
           

2.2 數組中出現次數超過一半的數字

數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，是以輸出2。如果不存在則輸出0。

2.2.1 思路1

思路：

• 首先求出數組長度
• 其次統計每個數字出現的次數！昨天好像有一個方法實作了！回去看一下！想起來了！直接使用

  count

  函數+

  filter

  函數

2.2.2 代碼1

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        # 清單長度
        n = len(numbers) / 2
        a = list(set(list(filter(lambda x: numbers.count(x) > n, numbers))))
        if len(a) == 0:
            return 0
        else:
            return a[0]
           

2.2.3 思路2

先排序！

• 使用快速排序！然後如果某一個數字的出現次數大于數組一半的長度，那麼中間的數肯定就是它了！
• 然後統計中間數出現了多少次！大于一半則ok！
• 注意考慮邊界情況！隻有一個元素的list！
• 快排時間複雜度為 O ( N l o g N ) O(NlogN) O(NlogN)

2.2.4 代碼2

class Solution:
    
    def quick_sort(self, alist, first, last):
        # 快排
        if first >= last:
            return 
        
        # 定義兩個遊标+中值
        low = first
        high = last
        mid = alist[first]
        
        while low < high:
            while alist[high] >= mid and high > low:
                high -= 1
            alist[low] = alist[high]
            
            while alist[low] < mid and low < high:
                low += 1
            alist[high] = alist[low]
        
        alist[low] = mid
        
        # 遞歸
        self.quick_sort(alist, first, low-1)
        self.quick_sort(alist, low+1, last)
        
        return alist
        
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        # 考慮特殊情況
        if len(numbers) == 1:
            return numbers[0]
        # 首先快速排序
        alist = self.quick_sort(numbers, 0, len(numbers)-1)
        print(alist)
        # 判斷-看中值出現的次數是否大于一半！因為如果有 肯定中值為出現最多的之一！否則不可能！
        n = int(len(alist)/2)
        # 中值為：
        mid = alist[n]
        # 看有多少個中值！
        count = 0
        for j in alist:
            if j == mid:
                count += 1
        if count > len(alist)/2 :
            return mid
        else:
            return 0
           

2.3 連續子數組的最大和

HZ偶爾會拿些專業問題來忽悠那些非計算機專業的同學。今天測試組開完會後,他又發話了:在古老的一維模式識别中,常常需要計算連續子向量的最大和,當向量全為正數的時候,問題很好解決。但是,如果向量中包含負數,是否應該包含某個負數,并期望旁邊的正數會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續子向量的最大和為8(從第0個開始,到第3個為止)。給一個數組，傳回它的最大連續子序列的和，你會不會被他忽悠住？(子向量的長度至少是1)

2.3.1 思路1

• 如何考慮呢？
• 肯定沒法暴力去搜尋啊，因為組合太多了，肯定搞不過來的！那有沒有簡單的方法呢？判斷正負号？或者說有什麼規律或者結論？真想不到！

一個牛逼的思路：

即遇到求和為負數則重新規整為0開始！如果一開始就是負數也添加到全局list中，以防全部為負數！（特殊情況）

2.3.2 代碼1

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        # 法1 找到了規律！
        n = len(array)
        if n==1:
            return array[0]
        
        res = []
        s = 0
        for i in array:
            s += i
            if s > 0:
                # 如果累加和大于0 append到res 繼續
                res.append(s)
            else:
                # 如果累加和小于0 s歸為0 重新開始 并添加到res
                res.append(s)
                s = 0
        return max(res)
           

2.3.3 思路2

每一步求和 然後和之前的和取max！！！哇 這個思路牛逼啊！但是有一個問題！怎麼斷掉前面累加和為負數的情況呢！使用動态規劃：

以 a r r a y = [ 1 , − 2 , 3 , 10 , − 4 , 7 , 2 , − 5 ] array=[1,-2,3,10,-4,7,2,-5] array=[1,−2,3,10,−4,7,2,−5]為例：

首先定義相關符号：

• F ( i ) F(i) F(i)：以 a r r a y [ i ] array[i] array[i]為末尾元素的子數組的和的最大值，子數組的元素的相對位置不變
• F ( i ) = m a x ( F ( i − 1 ) + a r r a y [ i ] ， a r r a y [ i ] ) F(i)=max(F(i-1)+array[i] ， array[i]) F(i)=max(F(i−1)+array[i]，array[i])
• r e s res res：所有子數組的和的最大值
• r e s = m a x ( r e s ， F ( i ) ) res=max(res，F(i)) res=max(res，F(i))

開始疊代進行：

• 第一步， F ( 0 ) = m a x ( F ( 0 ) + a r r a y [ 0 ] , a r r a y [ 0 ] ) = 1 F(0)=max(F(0)+array[0],array[0])=1 F(0)=max(F(0)+array[0],array[0])=1， r e s = m a x ( r e s ， F ( 0 ) ) = 1 res=max(res，F(0))=1 res=max(res，F(0))=1
• 第二步， F ( 1 ) = m a x ( F ( 0 ) + a r r a y [ 1 ] , a r r a y [ 1 ] ) = m a x ( 1 − 2 , − 2 ) = − 1 F(1)=max(F(0)+array[1],array[1])=max(1-2,-2)=-1 F(1)=max(F(0)+array[1],array[1])=max(1−2,−2)=−1， r e s = m a x ( r e s ， F ( 1 ) ) = 1 res=max(res，F(1))=1 res=max(res，F(1))=1
• 第三步， F ( 2 ) = m a x ( F ( 1 ) + a r r a y [ 2 ] , a r r a y [ 2 ] ) = m a x ( − 1 + 3 , 3 ) = 3 F(2)=max(F(1)+array[2],array[2])=max(-1+3,3)=3 F(2)=max(F(1)+array[2],array[2])=max(−1+3,3)=3， r e s = m a x ( r e s ， F ( 2 ) ) = 3 res=max(res，F(2))=3 res=max(res，F(2))=3 這一步就能有效的實作斷掉前面累加和為負數的情況！也是為什麼也要把最近的一個數也作為比較的對象，比較的就是前面所有的累加和！
• 第四步， F ( 3 ) = m a x ( F ( 2 ) + a r r a y [ 3 ] , a r r a y [ 3 ] ) = m a x ( 3 + 10 , 10 ) = 13 F(3)=max(F(2)+array[3],array[3])=max(3+10,10)=13 F(3)=max(F(2)+array[3],array[3])=max(3+10,10)=13， r e s = m a x ( r e s ， F ( 3 ) ) = 13 res=max(res，F(3))=13 res=max(res，F(3))=13
• 第五步， F ( 4 ) = m a x ( F ( 3 ) + a r r a y [ 4 ] , a r r a y [ 4 ] ) = m a x ( 13 − 4 , − 4 ) = 9 F(4)=max(F(3)+array[4],array[4])=max(13-4,-4)=9 F(4)=max(F(3)+array[4],array[4])=max(13−4,−4)=9， r e s = m a x ( r e s ， F ( 4 ) ) = 13 res=max(res，F(4))=13 res=max(res，F(4))=13
• 第六步， F ( 5 ) = m a x ( F ( 4 ) + a r r a y [ 5 ] , a r r a y [ 5 ] ) = m a x ( 9 + 7 , 7 ) = 16 F(5)=max(F(4)+array[5],array[5])=max(9+7,7)=16 F(5)=max(F(4)+array[5],array[5])=max(9+7,7)=16， r e s = m a x ( r e s ， F ( 4 ) ) = 16 res=max(res，F(4))=16 res=max(res，F(4))=16
• 第七步， F ( 6 ) = m a x ( F ( 5 ) + a r r a y [ 6 ] , a r r a y [ 6 ] ) = m a x ( 16 + 2 , 2 ) = 18 F(6)=max(F(5)+array[6],array[6])=max(16+2,2)=18 F(6)=max(F(5)+array[6],array[6])=max(16+2,2)=18， r e s = m a x ( r e s ， F ( 5 ) ) = 18 res=max(res，F(5))=18 res=max(res，F(5))=18
• 第八步， F ( 7 ) = m a x ( F ( 6 ) + a r r a y [ 7 ] , a r r a y [ 7 ] ) = m a x ( 18 − 5 , − 5 ) = 13 F(7)=max(F(6)+array[7],array[7])=max(18-5,-5)=13 F(7)=max(F(6)+array[7],array[7])=max(18−5,−5)=13， r e s = m a x ( r e s ， F ( 6 ) ) = 18 res=max(res，F(6))=18 res=max(res，F(6))=18

綜上！最大的子數組和為18！

2.3.4 代碼2

開始結合上面思路寫代碼：

# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        # 法1 找到了規律！
        n = len(array)
        if n==1:
            return array[0]
        
        s = 0
        l = 0
        res = float("-inf") # 不能取為0 因為可能全為負數！這樣就會出現bug
        for i in array:
            # l為中間過渡變量 表示遞歸的前n項最大和
            l = s+i
            # s為前多少項和 和 最近一個值的最大值！
            s = max(l, i)
            res = max(res,s)
        return res
           

2.4 把數組排成最小的數

輸入一個正整數數組，把數組裡所有數字拼接起來排成一個數，列印能拼接出的所有數字中最小的一個。例如輸入數組{3，32，321}，則列印出這三個數字能排成的最小數字為321323。

2.4.1 思路

• 拼接數字！還是看這個數字的個數位 十位的一個情況！多個數字比較深度！
• 但落實到代碼層面怎麼去考慮呢？不知道 有點懵逼啊！能不能暴力搜尋一下？n的階乘種排列方式！太複雜了！

牛逼的思路：

• 将每個數字都變成字元串！然後将字元串進行拼接成不同的數 然後再直接取字元串最小的！輸出對應的值即可！

2.4.2 代碼

# -*- coding:utf-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)
           

2.5 數組中的逆序對

2.5.1 題目

在數組中的兩個數字，如果前面一個數字大于後面的數字，則這兩個數字組成一個逆序對。輸入一個數組,求出這個數組中的逆序對的總數P。并将P對1000000007取模的結果輸出。 即輸出P%1000000007

2.5.2 思路1

直接暴力搜！

• 首先兩兩比較值的大小，求和逆序對總數P

2.5.3 代碼1

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

思路簡單，代碼也簡單，但是時間複雜度無法通過，為平方複雜度！想辦法優化！

2.5.4 思路2

太炫的思路了。

結論：逆序對的總數 = 左邊數組中的逆序對的數量 + 右邊數組中逆序對的數量 + 左右結合成新的順序數組時（注意：左右先進行升序排列！）中出現的逆序對的數量

為什麼呢？其實也很簡單！

• 首先分成兩部分沒問題，分别統計左右兩邊數組逆序對的數量
• 現在需要合并！但合并之後需要先對左右兩邊進行排序！因為防止左右兩邊内部再加一次！
• 是以就是歸并排序的思想！分治法！
• 但代碼還是有點難度的~

2.5.5 代碼2

# -*- coding:utf-8 -*-
class Solution:
    def InversePairs(self, data):
        # write code here
        if not data:
            return 0
        temp = [i for i in data]
        return self.mergeSort(temp, data, 0, len(data)-1) % 1000000007
       
    def mergeSort(self, temp, data, low, high):
        if low >= high:
            temp[low] = data[low]
            return 0
        mid = (low + high) / 2
        left = self.mergeSort(data, temp, low, mid)
        right = self.mergeSort(data, temp, 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]
                count += mid-i+1
                j += 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
           

2.6 數字在排序數組中出現的次數

2.6.1 題目

統計一個數字在排序數組中出現的次數。

2.6.2 思路1

• 直接循環周遊判斷
• 但加上一個條件 如果位置i等于一個值 但位置i+1不等于 那麼就break 因為數組是排序好的！

2.6.3 代碼1

# -*- coding:utf-8 -*-
class Solution:
    def GetNumberOfK(self, data, k):
        # write code here
        # 使用簡單的方法 循環周遊
        cnt = 0
        for i in range(len(data)):
            if data[i] == k:
                cnt += 1
            elif data[i] == k and data[i+1] != k:
                break
            else:
                continue
        return cnt
           

2.6.4 思路2

• 二分查找！這樣的複雜度會比上面的低，上面的複雜度為O(n)
• 首先通過二分查找找到該元素 然後再以該元素為中心分别向兩邊去擴散！去找 看有多少相同的！

2.6.5 代碼2

遇到的坑：

• 首先是二分查找得需要非遞歸版本 這樣才能傳回該找到的元素的位置
• 注意考慮邊界條件，即這個元素可能不存在！是以要先寫一個判斷！
• 注意将mid進行回歸！矯正到中值的位置！

# -*- coding:utf-8 -*-
class Solution:
    
    def Binary_search(self, data, k):
        # 二分查找
        n = len(data)-1
        start = 0
        end = n
        
        while start <= end:
            mid = (start + end) // 2
            if data[mid] < k:
                # right
                start = mid + 1
            elif data[mid] > k:
                # left
                end = mid - 1
            else:
                return mid
        return -1
        
    def GetNumberOfK(self, data, k):
        # write code here
        # 使用二分查找
        mid = self.Binary_search(data, k)
        if mid == -1:
            return 0
        else:
            cnt = 1

            while mid + 1 <= len(data)-1 and data[mid+1] == k:
                # 防止越界 + 符合條件
                mid += 1
                cnt += 1

            mid_org = mid - cnt + 1
            while mid_org - 1 >= 0 and data[mid_org - 1] == k:
                # 防止越界 + 符合條件
                mid_org -= 1
                cnt += 1

            return cnt
           

2.7 數組中隻出現一次的數字

2.7.1 題目

一個整型數組裡除了兩個數字之外，其他的數字都出現了兩次。請寫程式找出這兩個隻出現一次的數字。

2.7.2 思路1

• 暴力解法！直接周遊！
• 結果存入到字典！最後周遊字典即可！
• 注意下标！！！
• 以及注意字典判斷某個key是否存在的方法

2.7.3 代碼1

# -*- coding:utf-8 -*-
class Solution:
    # 傳回[a,b] 其中ab是出現一次的兩個數字
    def FindNumsAppearOnce(self, array):
        # write code here
        res = []
        dic = {}
        for i in range(len(array)):
            #if array[i] in dic:
            if array[i] in dic:
                dic[array[i]] += 1
            else:
                dic[array[i]] = 0
        for k,v in dic.items():
            if v == 0:
                res.append(k)
        return res
           

2.7.4 思路2

• 先排序！然後統計 如果次數為1
• 好像不太行的！！！
• 用的異或的思路！但是代碼太複雜了！忽略！

2.8 數組中重複的數字

2.8.1 題目

在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。 數組中某些數字是重複的，但不知道有幾個數字是重複的。也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。 例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數字2。

2.8.2 思路1

• 周遊！用一個字典來判斷！key為值 value為出現的次數
• 如果最後次數大于1則break！
• 記得加一個cnt來判斷是否進入了某一個循環！

2.8.3 代碼1

# -*- coding:utf-8 -*-
class Solution:
    # 這裡要特别注意~找到任意重複的一個值并指派到duplication[0]
    # 函數傳回True/False
    def duplicate(self, numbers, duplication):
        # write code here
        dic = {}
        cnt = 0 
        for num in numbers:
            if num in dic:
                dic[num] += 1
                if dic[num] == 2:
                    cnt += 1
                    duplication[0] = num
                    break
                else:
                    continue
            else:
                dic[num]=1
        if cnt != 0:
            return True
        else:
            return False
           

2.9 建構乘積數組

2.9.1 題目描述

給定一個數組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]。不能使用除法。

2.9.2 思路1

• 直接周遊！分兩段來！注意把每次循環空出一個位置來！！！
• 另外要注意不能一開始空list 然後直接指派！隻有append！或者說一開始賦予初始值 然後在這個基礎之上修改即可！

2.9.3 代碼1

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        n = len(A)
        B = list(range(n))
        # 基于分割點分别乘積得到結果
        for i in range(n):
            B[i] = 1
            # 第一段
            for j in range(i):
                B[i] *= A[j]
            # 第二段
            for k in range(i+1, n):
                B[i] *= A[k]
                   
        return B
           

3 參考

• https://blog.csdn.net/c406495762/article/details/79247243