Python tìm số dương nhỏ nhất trong danh sách

Tôi đang cố tìm số dương nhỏ nhất trong danh sách mà không sử dụng bất kỳ hàm tích hợp nào

Đây là những gì tôi đã cố gắng

def smallest_positive[lst]:
    smallest = lst[0]
    for i in lst:
        if [i > 0] and [smallest > i]:
            smallest = i
    return smallest

trường hợp thử nghiệm của tôi là

print[smallest_positive[[4, -6, 7, 2, -4, 10]]]
# outputs: 2 CORRECT

print[smallest_positive[[.22, 5, 3, -.1, 7, 6, 7]]]
# outputs: .22 CORRECT

print[smallest_positive[[-6, -7, -9]]]
# outputs: -6 INCORRECT # I expect output to be None

print[smallest_positive[[]]]
# outputs: Traceback INCORRECT # I expect output to be None

Một số trường hợp thử nghiệm không vượt qua

Chúng ta phải tìm số dương nhỏ nhất, vì vậy chúng ta có thể bỏ qua tất cả các số âm và bắt đầu tìm kiếm từ số nguyên dương nhỏ nhất là 1, v.v.  

Lưu ý rằng chúng ta không xét số nguyên 0 khi tìm số dương nhỏ nhất. Ta sẽ bắt đầu tìm từ số nguyên 1.
Nếu mảng đầu vào là.

Đầu vào. mảng1 = [2,9,-10,5,3,1,11,-1,7]

đầu ra. 4

Ở đây, chúng ta thấy có 1, có 2 và 3 nhưng không có 4 trong mảng do đó, 4 là số dương nhỏ nhất bị thiếu trong mảng

Đầu vào. mảng2 = [-10,4,-4,2,15,13,6,8,-1]

đầu ra. 1

Ở đây, số nguyên dương đầu tiên i. e. , thiếu 1

Đầu vào. mảng3 = [1,1,0,18,1,-12,-6,18,21]

đầu ra. 2

Trong ví dụ này, số nguyên dương đầu tiên i. e. , 1 có mặt nhưng tôi thứ hai. e. , 2 không có mặt

Ở đây, chúng ta sẽ thấy tổng cộng năm cách tiếp cận để giải quyết vấn đề này

1. Cách tiếp cận ngây thơ có độ phức tạp thời gian O[n2]
2. Cách tiếp cận dựa trên băm [độ phức tạp thời gian O[n] và không gian bổ sung O[n]]
   
3. Cách tiếp cận dựa trên sắp xếp có độ phức tạp thời gian O[nLogn]
   
4. Băm Boolean với độ phức tạp về thời gian O[n] và không gian bổ sung O[n]
5. Phương pháp hoán đổi nội tuyến với độ phức tạp thời gian O[n] và giải pháp không gian bổ sung O[1]
   
   

Cách tiếp cận ngây thơ có độ phức tạp thời gian O[n2]

Đây là một giải pháp Brute Force cho vấn đề. Chúng ta sẽ tìm kiếm tất cả các số nguyên dương bắt đầu từ 1. Chúng tôi biết số nguyên bị thiếu nhỏ nhất trong mảng sẽ nằm trong khoảng từ giá trị 1 đến size[array]+1. Trong trường hợp xấu nhất, chúng ta sẽ phải tìm n+1 số. Đối với mỗi giá trị số nguyên từ 1 đến size[array]+1, chúng ta sẽ phải duyệt qua toàn bộ mảng. Hãy xem việc thực hiện

def findNum[arr, n]:
    for i in range[1, n+1]:  # search for 1 to n+1 elements
        flag = False

        for j in range[n-1]:  # iterating through the array
            if arr[j] == i:
                flag = True
                break
        if flag == False:
            return i


arr = [-2, 2, 1, -3, 2, 10, 0]
length = len[arr]
res = findNum[arr, length]
print["The smallest positive missing number in the array is:",res]

Số bị thiếu dương nhỏ nhất trong mảng là. 3

Chúng tôi đang chuyển mảng chưa sắp xếp đầu vào cho hàm

def small_missNum[arr, size]:
    my_dict = dict[]

    for i in range[size]:
        if arr[i] > 0:
            if arr[i] not in my_dict.keys[]:
                my_dict[arr[i]] = 0
            else:
                my_dict[arr[i]] += 1

    index_val = 1

    while True:
        if index_val not in my_dict.keys[]:
            return index_val

        index_val += 1


# driver code
if __name__ == "__main__":
    arr = [1, 3, 2, 0, -1, 11,1]
    size = len[arr]

    print["The smallest positive missing number in the array is :", small_missNum[arr, size]]

1. Trong

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   6, chúng ta sẽ chạy hai vòng lặp for
2. Vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên ngoài sẽ chạy từ

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   9
3. Đối với mỗi giá trị của vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên ngoài, trước tiên chúng tôi sẽ đặt

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   0
4. Vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên trong sẽ duyệt qua toàn bộ mảng từ

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   2 cho mỗi giá trị của vòng lặp bên ngoài
5. Nếu chúng tôi tìm thấy giá trị hiện tại của vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên ngoài trong mảng, chúng tôi đặt

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   4 và không tiếp tục duyệt thêm bằng cách phá vỡ vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên trong
6. Nếu toàn bộ vòng lặp

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 bên trong được duyệt qua, thì

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   7 sẽ không bao giờ thay đổi thành

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   8 cho biết rằng phần tử không được tìm thấy trong mảng. Đó là

   def small_missNum[arr, size]:
       my_dict = dict[]
   
       for i in range[size]:
           if arr[i] > 0:
               if arr[i] not in my_dict.keys[]:
                   my_dict[arr[i]] = 0
               else:
                   my_dict[arr[i]] += 1
   
       index_val = 1
   
       while True:
           if index_val not in my_dict.keys[]:
               return index_val
   
           index_val += 1
   
   
   # driver code
   if __name__ == "__main__":
       arr = [1, 3, 2, 0, -1, 11,1]
       size = len[arr]
   
       print["The smallest positive missing number in the array is :", small_missNum[arr, size]]
   

   7sẽ vẫn là

   def merge_sort[arr]:                   # function to recursively divide the array
       if len[arr]