Cần giúp đỡ tối ưu bài toán tìm các phần tử đôi một khác nhau đều xuất hiện ở hai mảng a, b

#1

Chả là em đang làm thử thách tại trang codelearn.io, đề bài này cho 10 case có 5 case cho biết đầu vào, 5 case thì ẩn đầu vào đi. Em làm mãi mà chỉ đạt 9/10 do 1 case vượt quá thời gian chạy. Mọi người xem đề bài và code của em, rồi giúp em tối ưu code với ạ :frowning: em nghĩ mãi mà ko ra. Em cảm ơn ạ.
Đề bài:

Cho vào hai mảng a,b . Bạn hãy viết chương trình trả về mảng c gồm các phần tử đôi một khác nhau đều xuất hiện ở hai mảng a,b. Mảng c được trả về theo thứ tự từ bé đến lớn.

Ví dụ

Với a = [1, 2, 3, 1, 3] và b = [3, 2, 2, 3, 5, 6, 7, 4] thì addArray(arr) = [2, 3].

Đầu vào/Đầu ra:

  • [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, Go và JavaScript.
  • [Đầu vào] Array.Integer a,b
    0 <= a.length, b.length <= 10^5; 0 <= a[i], b[i] <= 10^5
    ``
  • [Đầu ra ]Array.Integer

Code của em:

        Set<Integer> mySet = new TreeSet<>();
        for(int i : a){
            for (int j : b) {
                if(i==j){
                    mySet.add(i);
                }
            }
        }

        return mySet;
    }

Cảm ơn mn rất nhiều ạ.

#2

Số lần lặp tối đa: 10^5 * 10^5 = 10^10 (10 tỷ) lần lặp.

3 Likes
#3

Ca này thật sự khó. Đến C/C++ chả làm gì ngoài việc duyệt từ 1 đến 1 tỷ cũng mất 3.5s vị chi cho 10 tỉ lần lặp mất 30s - 40s. Vậy khả năng mà chỉ 0.5s trên C/C++ hơi khó nhỉ. :frowning:

Thêm cái bằng chứng cho thuyết phục

image
image1600×900 194 KB

Về bài này thì anh thử dùng hashset xem sao. :disappointed:

2 Likes
#4 
Set<Integer> listA = Arrays.stream(a).collect(Collectors.toSet());
return Arrays.stream(b).distinct().filter(listA::contains).sorted().toArray(Integer[]::new);

Set<Integer> mySet = new TreeSet<>();
for(int i = 0; i < 10000; i += 1)
{
    if(a.contains(i) && b.contains(i))
        mySet.add(i);
}
return mySet;

Bạn cho mình link đề bài mình vô chơi thử với?

2 Likes
#5

stream(b).distinct() hình như hơi dư cái distinct :wink:

2 Likes
#6

Chắc là có cách gì đó mà mình chưa biết thôi bạn :v kkkk

2 Likes
#7

đây ạ

#8

em nghĩ cái này dùng vòng lặp ko ổn :frowning: nhưng chưa nghĩ ra cách khác

#9

Nếu b có 2 phần tử giống nhau thì result sẽ bị lặp.

2 Likes
#10

Bài này dùng mảng đánh dấu là chuẩn bài. Chỉ mất 2* 10^5 lần lặp là OK. 200k lần lặp thì java chạy cũng tầm 100ms là cùng

7 Likes
#11

mảng đánh dấu là sao ạ ? bác có thể cho em từ khoá tìm hiểu không ạ?

#12

Nó là kĩ thuật mảng đánh dấu ấy ạ.
Giả sử có 1 mảng a = { 1; 3 ;5 } và 1 mảng mark có 10 ^ 5 phần tử để đánh dấu chứa tất cả đều là giá trị 0 để đếm số lần xuất hiện chẳng hạn.
Bắt đầu duyệt từ đầu mảng a đến cuối mảng a. Giả sử khi gặp được phần tử 1 trong mảng a thì tăng giá trị của mark[1] thêm 1. Gặp phần tử 3 thì tăng mark[3] thêm 1. Sau khi chạy hết mảng a thì ta thu được :

Mảng mark : 0 1 0 1 0 1 0 0 0....
Index     : 0 1 2 3 4 5 6 7 8 ..
Lần lượt từ trái sang phải tương ứng với index đếm từ 0 tăng dần.

Đây là 1 kỹ thuật rất hay và thông dụng. Anh có thể search google theo từ khóa kĩ thuật mảng đánh dấu trong lập trình

7 Likes
#13

Sửa demo của anh @noz1995 một tí và update lại cho đúng (cảm ơn @Huy_Nguyen1 nhé :+1:).

// ArrayList<Integer> a, b;
Set<Integer> set_c = new TreeSet<Integer>(c);
Set<Integer> set_b = new TreeSet<Integer>(b);
c.retainAll(set_b);
return c;
5 Likes
#14

Bài này mục đích chắc để hiểu về set và các ops trên set :thinking:. C gồm các phần tử đôi 1 khác nhau -> tất cả các phần tử của c khác nhau. Và các phần tử của c đều thuộc a và b -> giao của 2 set. https://www.tutorialspoint.com/get-the-intersection-of-two-sets-in-java

4 Likes
#15

Như này chắc c sẽ có phần tử thuộc a mà k thuộc b :thinking:

4 Likes
#16

Đánh dấu phù hợp vs phần tử có giá trị nhỏ và các phần tử phân bố đều

2 Likes
#17

Đã update vào comment nhé.

4 Likes
#18

Đa tạ bác nhiều quá ạ :v làm theo bài bác gợi ý em đã làm dc rồi ạ :v Em cảm ơn bác ạ.

Em cũng gửi lời cảm ơn đến tất cả mn đã giúp đỡ và hướng dẫn em ạ. Em cảm ơn nhiều ạ.

3 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?