Hướng dẫn codility oddoccurrencesinarray solution python - codility Odoccurrencesinarray giải pháp python

Tôi đang cố gắng sử dụng đệ quy để giải quyết vấn đề kỳ lạ

• Chúng tôi được cung cấp một mảng với n phần tử, n luôn kỳ quặc
• Tất cả các phần tử của mảng ngoại trừ một người có tổng số lần xuất hiện
• Chúng ta cần viết mã trả về một giá trị không ghép đôi

Ví dụ: nếu mảng được đưa ra là [9, 3, 9, 3, 7, 9, 9], mã phải trả về 7, vì đó là phần tử duy nhất trong mảng không được ghép.

Giải pháp của tôi Pseudocode/quá trình suy nghĩ là:

• Sắp xếp mảng
• Nếu hai phần tử đầu tiên bằng nhau, hãy xóa chúng và chạy thuật toán giải pháp một lần nữa đệ quy trên mảng trừ hai phần tử đầu tiên (sau khi sắp xếp)
• Nếu hai phần tử đầu tiên không bằng nhau, phần tử đầu tiên của mảng phải là mục không ghép đôi

Việc thực hiện của tôi là:

def solution(A):
    # write your code in Python 3.6
    if len(A) > 1: 
        A = sorted(A)
        if A[0] != A[1]:
            return A[0]
        else:
            solution(A[2:])
    else:
        return A[0]

Tôi tiếp tục nhận được thông báo lỗi

Loại kết quả không hợp lệ, int mong đợi, tìm thấy. Lỗi thời gian chạy (chương trình được thử nghiệm chấm dứt với mã thoát 1)

Bất cứ ai có thể giúp tôi tìm ra điều này có nghĩa là gì và làm thế nào tôi có thể sửa nó? Về mặt thuật toán, tôi nghĩ rằng giải pháp của tôi là âm thanh và tôi không hiểu tại sao nó không trả về các giá trị số nguyên như tôi đã chỉ định.

hỏi ngày 5 tháng 1 lúc 18:44Jan 5 at 18:44

3

Một giải pháp python khác 100%

Có một giải pháp khác mà chúng ta có thể sử dụng logic XOR.

Trước tiên, chúng ta hãy nhớ với nhau có nghĩa là gì:

Vì vậy, chúng ta có thể nhận ra rằng nếu chúng ta có đầu vào A và đầu vào B cùng bit thì đầu ra XOR sẽ bằng không.Input A and Input B the same bit then, XOR Output will be zero.

Ngoài ra, nếu chúng ta lấy BIT XOR của bất kỳ số nào bằng 0 chắc chắn sẽ đưa ra cùng một số vì các bit của số sẽ dẫn đến cùng một bit có nghĩa là cùng một số.

Bây giờ, để giải quyết vấn đề với logic XOR, chúng tôi bắt đầu bằng cách xác định một số sẽ giữ kết quả của đầu ra XOR mỗi lần, vì vậy trước tiên, chúng tôi bắt đầu bằng 0 và tôi đã nói trước đó 0 với bất kỳ số nào cho cùng một số.

Nhưng nếu chúng ta nhận được một số khác nhau vào lần tới, kết quả XOR sẽ là một số không xác định.

Cuối cùng, chắc chắn số không được ghép nối sẽ được trả về.

Vì một giải pháp như thế này sẽ có thể chỉ với một vòng lặp, chúng tôi cần phải lặp qua tất cả các yếu tố và nếu chúng tôi phá vỡ vào một lúc nào đó, kết quả của XOR sẽ là một số chúng tôi không cần nên chúng tôi cần đảm bảo rằng chúng tôi lặp lại Thông qua toàn bộ mảng một lần và sau đó vì thực tế là bit xor của cùng một số sẽ trả về 0. Vì vậy, chúng tôi vẫn ở cuối với số không được ghép đôi với bất cứ điều gì.break at some point, the result of the XOR would be some number we do not need so we need to make sure that we loop through the whole array once and then because of the fact that bit XOR of the same number would return zero. so that we remain at the end with the number that is unpaired with anything.

Độ phức tạp thời gian được phát hiện: O (n) hoặc O (n*log (n))O(N) or O(N*log(N))

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

Funnydman

6.9773 huy hiệu vàng27 Huy hiệu bạc49 Huy hiệu đồng3 gold badges27 silver badges49 bronze badges

Đã trả lời ngày 1 tháng 2 lúc 9:25Feb 1 at 9:25

Tôi sẽ đề xuất một cách tiếp cận khác nhau hoàn toàn. Một cách tiếp cận đệ quy không chính xác, tuy nhiên các cuộc gọi lặp đi lặp lại đến

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

3 không hiệu quả, đặc biệt nếu đầu vào lớn đáng kể.

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  return list(s)

input = [9, 3, 9, 3, 7, 9, 9]
solve(input)

Chúng ta có thể hình dung

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

4 trong quá trình đánh giá -

{}     # <- initial s
{9}    # <- 9 is added
{9,3}  # <- 3 is added
{3}    # <- 9 is removed
{}     # <- 3 is removed
{7}    # <- 7 is added
{7,9}  # <- 9 is added
{7}    # <- 9 is removed

Cuối cùng

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

5 được trả về chuyển đổi

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

6 thành

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

7. Để xuất trình câu trả lời, chúng ta có thể viết một

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

8 đơn giản -

unpaired = solve(input)

if (len(unpaired) < 1):
  print("there are no unpaired elements")
elif (len(unpaired) > 1):
  print("there is more than one unpaired element")
else:
  print("answer:", unpaired[0])

Một tùy chọn khác là có

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

9 trả về phần tử không ghép đầu tiên hoặc

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  return list(s)

0 -

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  for v in s:
    return v          # <- immediately return first element

answer = solve(input)

if answer is None:
  print("no solution")
else:
  print("the solution is", answer)

Đã trả lời ngày 5 tháng 1 lúc 19:07Jan 5 at 19:07

MulanmulanMulan

123K29 Huy hiệu vàng217 Huy hiệu bạc249 Huy hiệu Đồng29 gold badges217 silver badges249 bronze badges

Bạn không trả lại bất cứ điều gì từ cuộc gọi đệ quy của bạn, điều đó có nghĩa là bạn đang trả lại

def solve(t):
  s = set()
  for v in t:
    s.add(v) if v not in s else s.remove(v)
  return list(s)

0.

Đã trả lời ngày 5 tháng 1 lúc 18:47Jan 5 at 18:47

SCOTT HUNTSCOTT HUNTERScott Hunter

47.5K11 Huy hiệu vàng56 Huy hiệu bạc95 Huy hiệu Đồng11 gold badges56 silver badges95 bronze badges

def solution(A):
    cloned = []
    A.sort()
    if len(A) > 1:
       for itr in A:
          if itr in cloned:
             itrindex = cloned.index(itr)
             cloned.pop(itrindex)
          else:
             cloned.append(itr)
    else:
        return A[0]

    return cloned[0]

Đã trả lời ngày 12 tháng 3 lúc 10:21Mar 12 at 10:21

1

Tôi đã thử nhiều cách nhưng hiệu suất không tốt hơn!

def solution(A):    
    for i in set(A):
    if A.count(i) == 1:
        return i

Điều này chỉ mang lại cho tôi một điểm hoàn hảo 25%. Tuy nhiên, tôi cũng đã thử cách khác.

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

0

Đây có thể là một giải pháp nhưng điểm hiệu suất chỉ là 50%. Không chắc chắn điều gì làm cho nó 100%. Vui lòng đăng nếu bạn nhận được 100% Perf cho thử thách này trong Codility.

Edit1:

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

1

Điều này đã giúp tôi có một điểm hoàn hảo 100%. Tham khảo: Codetrading (YouTube)

Đã trả lời ngày 5 tháng 9 lúc 11:27Sep 5 at 11:27

Nó có một cái gì đó đơn giản như thế này bằng cách sử dụng các hàm mảng PHP, nó có điểm 100% ở Codility, nghĩ rằng nó có thể giúp ích nếu Python có một số hàm mảng như thế này.

def solution(A): 
     
    num = 0

    for i in range(len(A)): 
        num = num ^ A[i]        
         
    return num

2

Đã trả lời ngày 14 tháng 6 lúc 22:02Jun 14 at 22:02