30/09/2018, 23:30

Bài toán tìm 2 phần từ trong mảng số nguyên N phần tử

Hôm nay lướt trên Facebook, em lượm được 1 bài như sau:

Cho một mảng số nguyên N phần tử, mỗi phần tử xuất hiện 2 lần, chỉ riêng
có HAI phần tử xuất hiện 1 lần duy nhất, yêu cầu tìm ra 2 phần tử đó.

Ví dụ: [2, 5, 1, 4, 3, 5, 3, 2] --> kết quả [1, 4]

Kì vọng: O(N) time và O(1) extra space complexity.
Mọi người cùng suy nghĩ làm cho vui nhé!

HINT: xử lý bit, XOR, bit khác nhau

... viết 01:31 ngày 01/10/2018

void Bit::BitHandler::getTwoNonRepeatElements(int * arr, int size, int * res1, int * res2)
{
	int XOR = 0;
	*res1 = 0;
	*res2 = 0;

	for (int i = 0; i < size; i++)
		XOR ^= arr[i];

	int rightMostBit = XOR & -XOR;

	for (int i = 0; i < size; i++)
	{
		if (arr[i] & rightMostBit)
			*res1 ^= arr[i];
		else
			*res2 ^= arr[i];
	}
}

Người bí ẩn viết 01:41 ngày 01/10/2018

Đáp án ở đây nhé mọi người: [spoiler] http://codepad.org/sAfVpPhk [/spoiler]

Đây là cách giải của 1 anh khá là giỏi về giải thuật có tên giống như vị thủ tưởng hiện tại của VN

Bình luận về bài viết này

Chia sẻ tin đăng đến bạn bè

Gửi Messenger

Bài liên quan

Người bí ẩn

0 chủ đề

0 bài viết

Tác giả nổi bật