Leetcodeブラシ問題【配列】第2/3の大きい数を求めます

速手筆記試験の原題:
リストを1つあげて、1回だけ遍歴して、中から2番目に大きい数を見つけます
解決策1:並べ替えてから値を取る
まずsort、自動昇順で並べ替え、

nums = [2，4，5，8]
nums_list = sorted(nums)
print('      ：',nums_list [-2])

知識点1:sortメソッド時間複雑度:O(n log n)pythonのsort内部実装メカニズム:Timesort,Timsortはマージソート(merge sort)と挿入ソート(insertion sort)を組み合わせたソートアルゴリズムの最悪時間複雑度:O(n log n)空間複雑度:O(n)
解決方法2:まず2つの数を初期化して、大きさを定義して、残りの値とこの2つのfirstとsecondの対比を取って、交換します
注意:初期のfirstとsecondはまず勝手に2つの数を取り、まず大きさを比較した後、残りの数はこの2つと比較して簡単になりました.

class  SecondNum(object):
    def get_second(self,nums):
        first=nums[0]
        second=nums[len(nums)-1]
        if first < second:
            second,first=first,second
        if len(nums)<2:
            return  "      2，     "
        else:
            for i in range(1,len(nums)-1):  #     >     ，        
                if nums[i]>=first:   #         first,            first ，   first    second
                    first,second=nums[i],first
                elif nums[i]>=second:
                    second=nums[i]
                else:
                    pass
            return [first,second]

leetcode 414の3番目の数
タイトルの要件:

        ，           。     ，          。            O(n)。

   1:

  : [3, 2, 1]

  : 1

  :        1.
   2:

  : [1, 2]

  : 2

  :         ,          2 .
   3:

  : [2, 2, 3, 1]

  : 1

  :   ，         ，            。
      2  ，      。

注意:ここにはいくつかの特殊な状況があります.

の長いが2の場合、2つの値のうち最大の

を出力必要がある.

長さが3の場合、重複データの考え方がある:上記の方法2と同様に、まず3つの初期値を探して、順序を並べてから次の数と1対1で時間複雑度を比較する:O(n)は始まったばかりなので、3つの数だけ並べ替えて、時間複雑度O(3)の下のforループは1回O(n)

である.

 def get_three(self,nums):
        if len(nums) < 3:
            if len(nums) == 2:
                first = nums[0]
                second = nums[len(nums) - 1]
                if first < second:
                    first, second = second, first
            else:
                return 0
            return first

        else:
            #      3         
            first = nums[0]
            second = nums[len(nums) - 1]
            third = nums[len(nums) - 2]
            if third > second:  #    3> 2 
                if first > third:  #   1> 3
                    second, third = third, second
                else:
                    if first > second:  #  1 > 2    1<  3
                        first, second, third = third, first, second
                    else:  #  1 
                        first, second, third = third, second, first
            else:
                #    3 <   2      1 
                if first < second:
                    if first > third:
                        first, second, third = second, first, third
                    else:
                        first, second, third = second, first, third
                else:
                    pass
            #       
            for i in range(1, len(nums) - 2):
                if nums[i]>=first:
                    first,second,third=nums[i],first,second
                else:
                    if nums[i]>second:
                        second,third=nums[i],second
                    else:
                        if nums[i]>third:
                            third=nums[i]
                        else:
                            pass
            return [first,second,third]