Tìm x số nguyên nhỏ nhất trong danh sách độ dài n

Question

Bạn có danh sách n số nguyên và bạn muốn x nhỏ nhất. Ví dụ:

x_smallest([1, 2, 5, 4, 3], 3) phải trả lại [1, 2, 3].

Tôi sẽ bỏ phiếu cho các thời gian chạy duy nhất trong lý do và sẽ kiểm tra màu xanh lá cây cho thời gian chạy tốt nhất.

Tôi sẽ bắt đầu bằng O(n * x): Tạo một mảng có độ dài x. Lặp lại qua danh sách x lần, mỗi lần kéo ra số nguyên nhỏ nhất tiếp theo.

Chỉnh sửa

• Bạn không có ý tưởng như thế nào dù lớn hay nhỏ những con số này trước thời hạn.
• Bạn không quan tâm đến lệnh cuối cùng, bạn chỉ muốn x nhỏ nhất.
• Điều này đã được xử lý trong một số giải pháp, nhưng giả sử rằng trong khi bạn không được đảm bảo một danh sách duy nhất, bạn cũng sẽ không nhận được danh sách thoái hóa, chẳng hạn như [1, 1, 1, 1, 1].

Answer 1

Bạn có thể tìm phần tử nhỏ nhất thứ k trong O (n) thời gian. This has been discussed on StackOverflow before. Có các thuật toán ngẫu nhiên tương đối đơn giản, chẳng hạn như QuickSelect, chạy trong O (n) thời gian dự kiến ​​và các thuật toán phức tạp hơn chạy trong trường hợp xấu nhất O (n).

Với phần tử nhỏ nhất thứ k bạn có thể thực hiện một lần vượt qua danh sách để tìm tất cả các phần tử nhỏ hơn k-thứ nhỏ nhất và bạn đã hoàn tất. (Tôi giả định rằng mảng kết quả không cần phải được sắp xếp.)

Thời gian chạy tổng thể là O (n).

Answer 2

Thêm tất cả số n vào một heap và xóa x của chúng. Mức độ phức tạp là O((n + x) log n). Vì x rõ ràng là nhỏ hơn n, nó là O(n log n).

Answer 3

Psudocode:

def x_smallest(array<int> arr, int limit) 
    array<int> ret = new array[limit] 

    ret = {INT_MAX} 

    for i in arr 
     for j in range(0..limit) 
      if (i < ret[j]) 
       ret[j] = i 
      endif 
     endfor 
    endfor 

    return ret 
enddef 

Answer 4

Trong mã giả:

y = length of list/2 

if (x > y) 
    iterate and pop off the (length - x) largest 
else 
    iterate and pop off the x smallest 

O (n/2 * x)?

Answer 5

sort array 
slice array 0 x 

Chọn thuật toán sắp xếp tốt nhất và bạn đã hoàn tất: http://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms

Answer 6

Duy trì danh sách các x cao nhất cho đến nay trong thứ tự sắp xếp trong một skip-list. Lặp lại qua mảng. Đối với mỗi phần tử, tìm vị trí sẽ được chèn vào danh sách bỏ qua (log x time). Nếu ở bên trong của danh sách, nó là một trong những x nhỏ nhất cho đến nay, do đó, chèn nó và loại bỏ các phần tử ở cuối danh sách. Nếu không thì không làm gì cả.

Thời gian O (n * log (x))

thực hiện thay thế: duy trì bộ sưu tập của x cao nhất cho đến nay trong một max-heap, so sánh từng phần tử mới với yếu tố hàng đầu của heap, và pop + chèn phần tử mới chỉ khi phần tử mới nhỏ hơn phần tử trên cùng. Vì so sánh với phần tử trên là O (1) và pop/insert O (log x), đây cũng là O (nlog (x))

Answer 7

Nếu phạm vi số (L) được biết, bạn có thể sửa đổi đếm sắp xếp.

given L, x, input[] 
counts <- array[0..L] 
for each number in input 
    increment counts[number] 
next 

#populate the output 
index <- 0 
xIndex <- 0 
while xIndex < x and index <= L 
    if counts[index] > 0 then 
     decrement counts[index] 
     output[xIndex] = index 
     increment xIndex 
    else 
     increment index 
    end if 
loop 

này có thời gian chạy của O (n + L) (với bộ nhớ overhead của O (L)) mà làm cho nó khá hấp dẫn nếu phạm vi là nhỏ (L < n log n).

Answer 8

Bạn có thể sắp xếp rồi lấy giá trị x đầu tiên?

Java: với Sắp xếp nhanh O (n log n)

import java.util.Arrays; 
import java.util.Random; 

public class Main { 

    public static void main(String[] args) { 
     Random random = new Random(); // Random number generator 
     int[] list = new int[1000]; 
     int lenght = 3; 

     // Initialize array with positive random values 
     for (int i = 0; i < list.length; i++) { 
      list[i] = Math.abs(random.nextInt()); 
     } 

     // Solution 
     int[] output = findSmallest(list, lenght); 

     // Display Results 
     for(int x : output) 
      System.out.println(x); 
    } 

    private static int[] findSmallest(int[] list, int lenght) { 
     // A tuned quicksort 
     Arrays.sort(list); 
     // Send back correct lenght 
     return Arrays.copyOf(list, lenght);  
    } 

} 

của nó khá nhanh.

Answer 9

private static int[] x_smallest(int[] input, int x) 
    { 
     int[] output = new int[x]; 
     for (int i = 0; i < x; i++) { // O(x) 
      output[i] = input[i]; 
     } 

     for (int i = x; i < input.Length; i++) { // + O(n-x) 
      int current = input[i]; 
      int temp; 

      for (int j = 0; j < output.Length; j++) { // * O(x) 
       if (current < output[j]) { 
        temp = output[j]; 
        output[j] = current; 
        current = temp; 
       } 
      } 
     } 

     return output; 
    } 

Nhìn vào mức độ phức tạp: O (x + (nx) * x) - giả sử x là một số không đổi, O (n)

Answer 10

def x_smallest(items, x): 
    result = sorted(items[:x]) 
    for i in items[x:]: 
     if i < result[-1]: 
      result[-1] = i 
      j = x - 1 
      while j > 0 and result[j] < result[j-1]: 
       result[j-1], result[j] = result[j], result[j-1] 
       j -= 1 
    return result 

Trường hợp xấu nhất là O (x * n), nhưng thường sẽ gần hơn với O (n).

Answer 11

Điều gì về việc sử dụng splay tree? Bởi vì cách tiếp cận độc đáo của cây splay để cân bằng thích nghi nó làm cho việc thực hiện trơn tru của thuật toán với lợi ích bổ sung là có thể liệt kê các mục x theo thứ tự sau đó. Đây là một số psuedocode.

public SplayTree GetSmallest(int[] array, int x) 
{ 
    var tree = new SplayTree(); 
    for (int i = 0; i < array.Length; i++) 
    { 
    int max = tree.GetLargest(); 
    if (array[i] < max || tree.Count < x) 
    { 
     if (tree.Count >= x) 
     { 
     tree.Remove(max); 
     } 
     tree.Add(array[i]); 
    } 
    } 
    return tree; 
} 

Các GetLargest và Remove hoạt động có độ phức tạp khấu hao của O (log (n)), nhưng vì mục truy cập lần cuối bong bóng để đầu nó thường sẽ là O (1). Vì vậy, không gian phức tạp là O (x) và độ phức tạp thời gian chạy là O (n * log (x)). Nếu mảng xảy ra đã được đặt hàng thì thuật toán này sẽ đạt được độ phức tạp của trường hợp tốt nhất của O (n) với mảng tăng dần hoặc giảm dần. Tuy nhiên, một thứ tự rất kỳ quặc hoặc kỳ quặc có thể dẫn đến độ phức tạp O (n^2). Bạn có thể đoán làm thế nào mảng sẽ phải được đặt hàng cho điều đó xảy ra?

Answer 12

Trong scala, và có lẽ ngôn ngữ chức năng khác, không có trí tuệ:

scala> List (1, 3, 6, 4, 5, 1, 2, 9, 4) sortWith (_<_) take 5 
res18: List[Int] = List(1, 1, 2, 3, 4)