#include <iostream>
/*
* Merges two sorted arrays into a third sorted array
* without duplicates.
*
* Parameters:
* arr1, size1 - first sorted array and its size
* arr2, size2 - second sorted array and its size
* result - output array (must be large enough)
*
* Returns:
* Number of elements stored in result.
*
* Example:
* arr1 = {1, 2, 2, 3, 7, 7, 7, 8, 9}
* arr2 = {0, 0, 4, 4, 4, 5, 6, 7, 7, 8}
*
* Result:
* {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
*
* Time Complexity: O(n + m)
* Space Complexity: O(n + m)
*/
std::size_t mergeSortedUnique(
const int arr1[],
std::size_t size1,
const int arr2[],
std::size_t size2,
int result[])
{
std::size_t i = 0; // Index for arr1
std::size_t j = 0; // Index for arr2
std::size_t k = 0; // Index for result
while (i < size1 && j < size2)
{
int value;
if (arr1[i] < arr2[j]) {
value = arr1[i++];
}
else if (arr1[i] > arr2[j]) {
value = arr2[j++];
}
else {
// Same value exists in both arrays.
value = arr1[i];
++i;
++j;
}
// Append only if this value is not already
// the last value inserted into the result.
if (k == 0 || result[k - 1] != value) {
result[k++] = value;
}
}
// Process remaining elements from arr1.
while (i < size1) {
int value = arr1[i++];
if (k == 0 || result[k - 1] != value) {
result[k++] = value;
}
}
// Process remaining elements from arr2.
while (j < size2) {
int value = arr2[j++];
if (k == 0 || result[k - 1] != value) {
result[k++] = value;
}
}
return k;
}
int main()
{
const int arr1[] = {1, 2, 2, 3, 7, 7, 7, 8, 9};
const int arr2[] = {0, 0, 4, 4, 4, 5, 6, 7, 7, 8};
constexpr std::size_t size1 = sizeof(arr1) / sizeof(arr1[0]);
constexpr std::size_t size2 = sizeof(arr2) / sizeof(arr2[0]);
// Maximum possible size is size1 + size2.
int result[size1 + size2];
std::size_t resultSize =
mergeSortedUnique(arr1, size1, arr2, size2, result);
std::cout << "Merged array: ";
for (std::size_t i = 0; i < resultSize; ++i)
{
std::cout << result[i];
if (i + 1 < resultSize) {
std::cout << ", ";
}
}
}
/*
run:
Merged array: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
*/
