Hỏi về một bài toán trong codesignal

#1

Khi làm bài trong codesignal thì e gặp phải bài này

Given an array a that contains only numbers in the range from 1 to a.length, find the first duplicate number for which the second occurrence has the minimal index. In other words, if there are more than 1 duplicated numbers, return the number for which the second occurrence has a smaller index than the second occurrence of the other number does. If there are no such elements, return -1.
Example
For a = [2, 1, 3, 5, 3, 2], the output should be
firstDuplicate(a) = 3.
For a = [2, 4, 3, 5, 1], the output should be
firstDuplicate(a) = -1.
[execution time limit] 0.5 seconds (cpp)
[input] array.integer a
Guaranteed constraints:
1 ≤ a.length ≤ 105,
1 ≤ a[i] ≤ a.length.
[output] integer
The element in a that occurs in the array more than once and has the minimal index for its second occurrence. If there are no such elements, return -1.

Và đây là hàm của e, ý tưởng là dùng hai vòng lặp test hết các phần tử trong mảng để tìm chỉ số giống nhau

int firstDuplicate(std::vector<int> a)
{
	int length = a.size(), duplicate = -1; \\duplicate là giá trị của phần tử lặp lại
	for (int i = 0; i<length; i++)
	{
		for (int j = i + 1; j<length; j++) //dùng hai vòng lặp để test tất cả phần tử
		{
			if (a[i] == a[j] && j<length) //length ở đây là chỉ số của phần tử lặp lai thứ hai
			{
				duplicate = a[i]; \\ 
				length = j; 
				break;
			}
		}


	}
	return duplicate;
}

Hàm ban đầu của e ổn nhưng đến test thứ 21 lại quá thời gian nên e thử làm theo hướng khác.

Ý tưởng là khi gặp hai phần tử giống nhau thì bỏ vòng lặp cũ dùng vòng mới test các số giữa hai phần tử đó rồi cứ lặp lại như thế đến khi . Nhưng phần đệ quy thì e hơi yếu nên viết ra hàm ra kq sai

int truedup(std::vector<int> a, int i,int length,int duplicate)
{
   if (i<length)   
   {
      for  (i;i<length;i++)
      {      
         int j=i+1,templength=length;
         for (j;j<length;j++)            
         {                 
            if  (a[i]==a[j] && j<length)              
            {            
               duplicate=a[i];               
               templength=j;                         
               break;               
            }            
         }
         if (templength<length) { length=templength;  break; }          
      }
      truedup(a,i,length,duplicate);
   }
    return duplicate;
}   

int firstDuplicate(std::vector<int> a) 
{
   return truedup(a,0,a.size(),-1);
}
//Chương trình hơi xấu (nhiều phần làm đại k hiểu gì) nên nếu khó hiểu nên mọi người thông cảm.

Em muốn biết e sai chỗ nào, hoặc nếu cả chương trình e không đúng thì cho tham khảo ý tưởng. E xin cảm ơn

#2

Mình có một cách khác :smile:
Tạo một mảng int[] là temp. Sau đó chạy một vòng for để duyệt từng phần tử của mảng Input, mỗi lần chạy thì kiểm tra xem temp có chứ phần tử đó không ? Nếu có thì đó sẽ là số cần tìm, không thì add vào mảng temp

1 Like
#3

Như vậy thì có phải vẫn dùng hai vòng lặp đúng k? Mình sợ 2 vòng lặp nó chậm nữa

#4

Đúng là vẫn sẽ phải dùng 2 vòng for, nhưng số lượng sẽ ít hơn nên sẽ tối ưu hơn là dùng Đệ Quy nhỉ :smile: Với lại mình làm cách này trên CodeSignal thì không bị Time Limit đâu :joy: Bạn thử xem

1 Like
#5

Chú ý tiểu tiết nhé:
Vì a[i] <= a.length nên đảm bảo a[i] sẽ không quá to. Ý tưởng là tạo mảng b với mỗi phần tử b[i] đại diện cho số lần i xuất hiện trong a.

Bạn tạo mảng b với b.length = a.length, duyệt a. Mỗi lần gặp a[i] thì tăng b[ a[i] ] lên 1, nếu thấy cái nào lên 2 thì return ra a[i] luôn. Nếu duyệt hết a mà không có gì thì return -1.

image
image.png1920×1080 161 KB

3 Likes
#6

Đơn giản vậy. Mình cảm ơn nha :slight_smile:

#7

Mình có thêm một ý tưởng cho bạn là bạn hãy sắp xếp lại mảng đó trước rồi cho một vòng lặp for để tìm hai phần tử giống nhau

#8

Làm vậy sẽ tốn khá nhiều thời gian, tính ra phải chạy đến 3 vòng for lận. Mà làm vậy thì cũng không biết được vị trí xuất hiện của phần tử ở mảng gốc :smile:

1 Like
#9

Dữ liệu cho có dạng đặc biệt mà :smiley: chỗ này đọc không kĩ là sẽ bỏ qua.

Nếu tổng quát thì dùng set O(n) mem và O(nlogn) time.

1 Like
#10

Ta có thể lưu lại vị trí ban đầu của phần tử đó mà. Đâu cứ sort xong là không thể biết vị trí gốc của nó

2 Likes
#11

Vậy xin hỏi bạn sẽ lưu vị trí thế nào khi mà dữ liệu cho là một mảng có các phần tử trùng nhau ?? Chưa kể vậy thì việc lưu vị trí lại thì sẽ tốn thêm 1 cái for nữa?? Tức là 4 lần for @@

#12

Quất thêm 1 mảng idx lưu vị trí gốc, trong void sort lúc tráo item a[i], a[j] thì tráo luôn idx[i], idx[j] :smile:

3 Likes
#13

Đúng như bạn nói. Để lưu lại chỉ số ban đầu thì mình phải mất thêm 1 vòng for. Tuy nhiên, đây là ý tưởng của mình. Có thể nó phức tạp và kém hiệu quả hơn cách kia nhưng nó vẫn khả thi nên mình chia sẻ

1 Like
#14

Vậy thì xuân hòa à :smiley: đã lập mảng đồng hành idx[1…n] rồi thì truy cập a[idx[i]] thôi :smiley: mảng cũ a[] để nguyên không đổi gì cả.

2 Likes
#15

Bài này thực ra rất đơn giản bạn có thể làm như sau :

public static int firstDuplicate (int[] a) {
	Set<Integer> set = new HashSet<Integer>();
	for(int i : a) {
		int lengthBefore = set.size();
		set.add(i);
		if(lengthBefore == set.size()) {
			return i;
		}
	}
	return -1;
}

Chỉ cần 1 vòng lăp for là được kết quả !

Đây mà viết bằng java , nếu là c++ thì thay HashSet bằng unordered_set

#16

Dạng đặc biệt thì cần gì hash với tree :slight_smile: O(n) mem và time, như post #5. Vote close.

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