Xác định nếu một số chỉ xuất hiện một lần trong một mảng

Question

Đây là một câu hỏi về bài tập về nhà, tôi đã suy nghĩ về nó một thời gian, và đã đưa ra một vài giải pháp nhưng tôi nghĩ một số khác tốt hơn.

Cách nhanh nhất để xác định xem có phần tử (int) trong mảng chỉ xuất hiện một lần không? Bất kỳ phần tử nào cũng có thể xuất hiện bất kỳ số lần nào. {3, 1, 4, 1, 4, 3} sẽ trả về false trong khi {3, 1, 4, 1, 4, 1} sẽ trả về true (3 xuất hiện một lần).

Chúng tôi chỉ được phép sử dụng những thứ chúng tôi đã học (tất cả các khái niệm cơ bản, đệ quy, oop, tìm kiếm và sắp xếp các thuật toán, bao gồm cả quicksort) để tạo bảng băm không phải là một tùy chọn.

Cho đến nay giải pháp thực tế tốt nhất mà tôi đưa ra là phân loại nó bằng cách sử dụng quicksort rồi đi qua nó (O (nlogn)), giải pháp không thực tế tốt nhất mà tôi đưa ra là tạo một mảng lớn kích thước của tất cả các giá trị int có thể và sau đó sử dụng vị trí của nó tương tự như bảng băm (nhưng mảng đó quá lớn để thực hiện) (O (n))

Có cách nào khác (thực tế) để thực hiện điều này trong thời gian O (n) không?

EDIT: vừa nhận được câu trả lời từ TA, giải pháp O (n) được đề xuất mà tôi nghe nói là một giải pháp không thực tế (giống hoặc tương tự với những gì tôi đề xuất) và do đó họ bảo chúng tôi không sử dụng. Tôi chắc chắn 99% rằng câu trả lời thực tế tốt nhất (không có bảng băm) là thời gian O (nlogn).

Answer 1

Bạn có thể sử dụng quicksort tùy chỉnh để tìm các giá trị khác biệt mà không cần lặp qua mảng được sắp xếp sau đó.

Khi bạn đã chọn giá trị trục và di chuyển qua phần tương ứng của mảng, NẾU giá trị khớp với trục, loại bỏ giá trị đó VÀ loại bỏ giá trị trục sau khi bạn di chuyển qua một phần của mảng, điều này sẽ loại bỏ trùng lặp TRƯỚC KHI mảng được sắp xếp.

ví dụ:

Sorting [5, 1, 4, 1, 4, 1] 
If you choose the pivot as 4, you'd end up with the 2 sub arrays being: 
[1, 1, 1] and [5] 

Nếu trục của bạn không bao giờ bị loại bỏ, nó là khác biệt, nếu nó được bỏ đi làm quá trình tương tự trên các danh sách con. Nếu một danh sách phụ chỉ có 1 phần tử, nó sẽ khác biệt.

Bằng cách này, bạn có thể nhận các giá trị khác biệt MUCH trước đó.

Chỉnh sửa: Có điều này vẫn bị ràng buộc bởi O (nlogn) (tôi nghĩ vậy?)

Answer 2

Về cơ bản, bạn phải thực hiện so sánh kiểu phân loại bong bóng. Không có chức năng tích hợp để trả lời vấn đề, và thậm chí nếu bạn sắp xếp, bạn vẫn phải lặp qua mọi phần tử (thậm chí chỉ để tìm khi các nhóm bị hỏng). Bạn có thể thực hiện một số cách tiếp cận phức tạp hơn với nhiều mảng, đặc biệt nếu bạn cần tìm các phần tử nào chỉ trả về một lần.

Nhưng một khi bạn tìm thấy thẻ xuất hiện một lần, bạn có thể ngắt. Mã này sẽ làm điều đó. Đó là O (n^2), nhưng tôi không chắc chắn bạn có thể làm nhanh hơn cho vấn đề này.

boolean anySingles(int[] data]) 
{ 
outer: 
for (int i = 0; i < data.length - 1; i++) 
{ 
    for (int j = 0; i < data.length; j++) 
    { 
    if (i != j) 
    { 
    if (data[i] == data[j]) continue outer; 
    } 
    } 
    // made it to the end without finding a duplicate 
    return true; 
} 
return false; 
} 

Answer 3

Hãy làm một thí nghiệm:

package test; 

import java.util.Arrays; 
import java.util.HashSet; 
import java.util.Random; 
import java.util.Set; 

/** 
* Created with IntelliJ IDEA. 
* User: Nicholas 
* Date: 15.05.13 
* Time: 21:16 
*/ 
public class Searcher { 

    private static boolean searchBySorting(int [] array){ 
     int [] newArray = new int[array.length]; 
     System.arraycopy(array, 0, newArray,0, array.length); 

     Arrays.sort(newArray); 
     for (int i = 0; i < newArray.length - 2; ++i){ 
      if(newArray[i] == newArray[i + 1]){ 
       return true; 
      } 
     } 

     return false; 
    } 

    private static boolean searchByCompare(int [] array){ 
     int [] newArray = new int[array.length]; 
     System.arraycopy(array, 0, newArray,0, array.length); 

     for (int i = 0; i < newArray.length - 1; ++i){ 
      int value = newArray[i]; 
      for(int j = i + 1; j < newArray.length - 1; ++j){ 
       if(value == newArray[j]){ 
        return true; 
       } 
      } 
     } 

     return false; 
    } 

    private static boolean searchBySet(int [] array){ 
     int [] newArray = new int[array.length]; 
     System.arraycopy(array, 0, newArray,0, array.length); 

     Set<Integer> set = new HashSet<Integer>(); 
     for (int i = 0; i < newArray.length; ++i){ 
      if(set.contains(newArray[i])){ 
       return true; 
      } 

      set.add(newArray[i]); 
     } 

     return false; 
    } 

    private static int [] generateRandomArray(){ 
     Random random = new Random(); 
     int size = random.nextInt(1000) + 100; 
     int [] array = new int[size]; 

     for (int i = 0; i < size; ++i){ 
      array[i] = random.nextInt(); 
     } 

     return array; 
    } 

    public static void main(String [] args){ 

     long sortingTime = 0; 
     long compareTime = 0; 
     long setTime = 0; 

     for (int i = 0; i < 1000; ++i){ 
      int [] array = generateRandomArray(); 

      long begin = System.currentTimeMillis(); 
      for(int j = 0; j < 100; ++j){ 
       searchBySorting(array); 
      } 
      long end = System.currentTimeMillis(); 
      sortingTime += (end - begin); 

      begin = System.currentTimeMillis(); 
      for(int j = 0; j < 100; ++j){ 
       searchByCompare(array); 
      } 
      end = System.currentTimeMillis(); 
      compareTime += (end - begin); 

      begin = System.currentTimeMillis(); 
      for(int j = 0; j < 100; ++j){ 
       searchBySet(array); 
      } 
      end = System.currentTimeMillis(); 
      setTime += (end - begin); 
     } 

     System.out.println("Search by sorting: " + sortingTime + " ms"); 
     System.out.println("Search by compare: " + compareTime + " ms"); 
     System.out.println("Search by insert: " + setTime + " ms"); 
    } 
} 

kết quả của tôi:

Tìm kiếm bằng cách phân loại: 2136 ms

Tìm kiếm theo so sánh: 11955 ms

Tìm kiếm theo chèn: 4151 ms

Có câu hỏi nào không?

PS. Thuật toán tốt nhất tôi biết là Tortoise and hare