アレイアルゴリズム

配列アルゴリズムの概要
2 D配列の検索(各行の最後の検索)

# -*- coding:utf-8 -*-
class Solution:
    # array     
    def Find(self, target, array):
        # write code here
        if not array:
            return None
        row = len(array) -1
        col = len(array[0]) -1
        i = row
        j = 0
        while j <= col and i>=0:
            if array[i][j] < target:
                j +=1
            elif array[i][j] > target:
                i -=1
            else:
                return True
        return False

回転配列の最小数値(二分検索)

# -*- coding:utf-8 -*-
class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        L = len(rotateArray)
        a = L-1
        b = 0
        if L == 0:
            return 0

        while b < a:
            if rotateArray[b] < rotateArray[a]:
                return rotateArray[b]
            mid = (a-b) // 2 + b
            if rotateArray[mid] < rotateArray[a]:
                a = mid
            elif rotateArray[mid] > rotateArray[b]:
                b = mid +1
            else:
                b = b+1
        return rotateArray[b]          

奇数が偶数の前になるように配列の順序を調整します

class Solution:
    def reOrderArray(self, array):
        # write code here
        if not array:
            return []
        index = 0
        for i in range(len(array)):
            if array[index] %2 ==0:
                array.append(array.pop(index))
            else:
                index +=1
        return array

配列の半分を超える数値

# -*- coding:utf-8 -*-
class Solution:
    def MoreThanHalfNum_Solution(self, numbers):
        # write code here
        if not numbers:
            return None
        l = len(numbers)
        count = 1
        tem = numbers[0]
        for i in range(l):
            if count == 0:
                tem = numbers[i]
            if numbers[i] == tem:
                count +=1
            elif numbers[i] != tem:
                count -=1
        return tem if sum(tem == x for x in numbers) > l//2 else 0

配列を最小にする

# -*- coding:utf-8 -*-
class Solution:
    def PrintMinNumber(self, numbers):
        # write code here
        if not numbers:
            return ""
        numbers = list(map(str,numbers))
        numbers.sort(cmp = lambda x,y :cmp(x+y, y+x))
        return "".join(numbers).lstrip('0') or '0'

配列内の逆順序ペア(集計ソート)

# -*- coding:utf-8 -*-

class Solution:
    def InversePairs(self, data):
        #         ，              index     
        #      ，      index （        ，        ）              
        #       ，           
        _,s=self.MergeSort(data)
        return s%1000000007
     
    def MergeSort(self,data):
        n=len(data)
        #   
        if n==1:return data, 0
        #      
        part1,part2=data[:n//2],data[n//2:]
        sorted_part1,s1=self.MergeSort(part1)
        sorted_part2,s2=self.MergeSort(part2)
        #        ，      ，           
        s,sorted_temp=0,sorted_part1+sorted_part2
        # p、q        ，  q          index 
        p,q,len1,len_all=0,sorted_temp.index(sorted_part2[0]),len(sorted_part1),len(sorted_temp)
        while p<len1 and q<len_all:
            #  p p          ，          
            while p<len1:
                if sorted_temp[q]<sorted_temp[p]:
                    s+=len1-p
                    break
                p+=1
            q+=1
        #    ，                 
        l=[]
        p,q=0,sorted_temp.index(sorted_part2[0])
        while p<len1 and q<len_all:
            if sorted_temp[p]<sorted_temp[q]:
                l.append(sorted_temp[p])
                p+=1
            else:
                l.append(sorted_temp[q])
                q+=1
        if p==len1:l+=sorted_temp[q:]
        if q==len_all:l+=sorted_part1[p:]
        return l,s+s1+s2

数値が整列配列に現れる回数(二分検索)

class Solution:
    #      k    
    def BinarySearch(self, data, mlen, k):
        start = 0
        end = mlen - 1
        while start <= end:
            mid = (start + end) / 2
            if data[mid] < k:
                start = mid + 1
            elif data[mid] > k:
                end = mid - 1
            else:
                return mid
        return -1
 
    def GetNumberOfK(self, data, k):
        # write code here
        mlen = len(data)
        #         k    
        index = self.BinarySearch(data, mlen, k)
        if index == -1:
            return 0
        #           
        count = 1
        for i in range(1,mlen):
            if index + i < mlen and data[index+i] == k:
                count += 1
            if index - i >= 0 and data[index-i] == k:
                count += 1
        return count

        

配列に一度しか現れない数字(ビット演算)

class Solution:
    def FindNumsAppearOnce(self, array):
        if not array:
            return []
        #  array          
        tmp = 0
        for i in array:
            tmp ^= i
        #   tmp    1   
        idx = 0
        while (tmp & 1) == 0:
            tmp >>= 1
            idx += 1
        a = b = 0
        for i in array:
            if self.isBit(i, idx):
                a ^= i
            else:
                b ^= i
        return [a, b]

    def isBit(self, num, idx):
        """
          num        idx    1
        :param num:   
        :param idx:          
        :return: num idx    1
        """
        num = num >> idx
        return num & 1

配列の中で繰り返される数字(2つの方法は思想が異なり、操作が悪い)

# -*- coding:utf-8 -*-
class Solution:
    #        ~              duplication[0]
    #     True/False
    def duplicate(self, numbers, duplication):
        index = 0
        while index < len(numbers):
            if numbers[index] == index:
                index += 1
            elif numbers[index] == numbers[numbers[index]]:
                duplication[0] = numbers[index]
                return True
            else:
                index_2 = numbers[index]
                numbers[index], numbers[index_2] = numbers[index_2], numbers[index]
        return False

def findDuplicate(self, nums: List[int]) -> int:
        #  nums          ，nums                  
        #     nums    ，       ，                  ，           
        
        #    ，          nums[0]
        slow, fast = 0, 0
        #       ，      
        slow, fast = nums[slow], nums[nums[fast]]
        #      ，slow fast  ，        
        while slow != fast:
            slow, fast = nums[slow], nums[nums[fast]]
        #  before，after          ，    
        before, after = 0, slow
        # before after   ，           
        while before != after:
            before, after = nums[before], nums[after]
            
        return before

積配列の構築(遡及思想)

# -*- coding:utf-8 -*-
class Solution:
    def multiply(self, A):
        # write code here
        if not A:
            return None
        res = []
        for i in range(len(A)):
            temp = A[i]
            b =1
            for j in range(len(A)):
                A[i] = 1
                b *=A[j]
            res.append(b)
            A[i] = temp
        return res