I hope i made my self clear enough in the title but if not i am here to explain my self i got an array from an input ( like Arr = {7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2} ).

we can use only 1 additional array (1 original 1 additional)

this is what i made so far : I made a new array named newArr and assigned it all the values Arr contains. i sorted it (because its requires time complexity of nlogn) and then moved duplicates to the end. this is what i got till now: 1,2,3,5,6,7,9,2,2,3,7,9

now what i can't figure out :

now i need to move the original digits to their place according to the main arr (Arr) exluding duplicates which duplicates still should be in the end of the array so what i need to get is:

7 3 1 2 9 5 6 2 2 3 7 9 (all the values in the arrays are positive and they can be bigger then
n-which is the size of the array and ofc they can be also smaller then n) i also need to return the number of original digits in the array the original number should stay in the same position and the duplicates in the end of the array their order doesn't matter.

from here we can't use another additional array only the current arrays that we have ( which are 2) i have been thinking about doing some kind of binary search but all of them went wrong.(like bin_search_first) and original binary and still couldn't manage it. can some one give me an hint?

here is the code at where i am

#define _CRT_SECURE_NO_WARNINGS

/*Libraries*/
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <string.h>

int* input_array(int);
int moveDuplicatesV2(int*, int);
void merge(int* a, int p, int q, int r);
void merge_sort(int* a, int first, int last); 
void swap(int* v, int* u);
int bin_search_first(int , int* , int );


int main()
{
    int arr[12] =  { 7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2 };
    int n = 12; 
    int k = 0;
    int first = 0;
    int last = n - 1;
    int mid = (first   last) / 2;
    int l = n - 1;
    int* D = arr   1;
    int j = 0;
    size_t dupes_found = 0;
    int* newArr = (int*)malloc(12 * sizeof(int));
    assert(newArr);
    for (int i = 0; i < n; i  )
    {
        newArr[i] = arr[i];
    }
    merge_sort(newArr, first, last);
    for (size_t i = 0; i < n - 1 - dupes_found;) 
    {
        if (newArr[i] == newArr[i   1])
        {
            dupes_found  ;
            int temp = newArr[i];
            memmove(&newArr[i], &newArr[i   1], sizeof(int) * (n - i - 1));
            newArr[n - 1] = temp;
        }
        else {
            i  ;
        }
    }
    j = 0;
    int key = 0;
    first = 0;
    for (int i = 0; i < n - dupes_found; i  )
    {
        key = newArr[i];
        first = bin_search_first(key, arr,n);
        swap(&newArr[i], &newArr[first]);
        newArr[first] = newArr[i];


    }

    for (int i = 0; i < n; i  )
    {
        arr[i] = newArr[i];
    }

    
    for (int i = 0; i < n; i  )
    {
        printf("%d", arr[i]);
    }
    return n - dupes_found;
}
void merge(int* a, int p, int q, int r)
{
    int i = p, j = q   1, k = 0;
    int* temp = (int*)malloc((r - p   1) * sizeof(int));
    assert(temp);
    while ((i <= q) && (j <= r))
        if (a[i] < a[j])
            temp[k  ] = a[i  ];
        else
            temp[k  ] = a[j  ];
    while (j <= r)
        temp[k  ] = a[j  ];
    while (i <= q)
        temp[k  ] = a[i  ];
    /* copy temp[] to a[]   */
    for (i = p, k = 0; i <= r; i  , k  )
        a[i] = temp[k];
    free(temp);
}
void merge_sort(int* a, int first, int last)
{
    int middle;
    if (first < last) {
        middle = (first   last) / 2;
        merge_sort(a, first, middle);
        merge_sort(a, middle   1, last);
        merge(a, first, middle, last);
    }
}

void swap(int* v, int* u)
{
    int temp;
    temp = *v;
    *v = *u;
    *u = temp;
}
int bin_search_first(int key, int* a, int n)
{
    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low   high) / 2; // low   (high - low) / 2
        if (key > a[mid])
            low = mid   1;
        else
            if (key < a[mid])
                high = mid - 1;
            else //key==a[mid]
                if ((low == high) || (a[mid - 1] < key))
                    return mid;
                else
                    high = mid - 1;
    }
    return -1;
}

CodePudding user response：

Here is my idea:

1. Sort the array (nlogn)
2. Loop over the array and for each value, save a pointer to its first occurence (n)
3. Loop over the original array and insert the value into a result array if it is the values first occurrence. Whether or not it is the first occurrence can be checked using the sorted array: each element in this array has an additional flag that will be set if the value has already been seen. So, search for the element using bsearch, if seen append to back of result array (order does not matter), if not seen append to beginning of array and set seen value. (nlogn, since bsearch doesn't need to seek the first element because it was precomputed thus logn, over the array n)

Here is an example code (you can replace the qsort by mergesort to make the algorithm actually nlogn, I just used qsort because it is given):

#include <stdio.h>
#include <stdlib.h>

struct arr_value {
    int value;
    int seen;
    struct arr_value *first;
};

int compar(const void *p1,const void *p2) {
    struct arr_value *v1 = (struct arr_value *)p1;
    struct arr_value *v2 = (struct arr_value *)p2;
    if(v1->value < v2->value) {
        return -1;
    } else if(v1->value == v2->value) {
        return 0;
    }
    return 1;
}

int main()
{
#define NumCount (12)
    int arr[NumCount] =  { 7, 3, 1, 2, 7, 9, 3, 2, 5, 9, 6, 2 };
    int arrResult[NumCount];
    int resultCount = 0;
    int resultCountBack = 0;
    struct arr_value arrseen[NumCount];
    for(int i = 0; i < NumCount;   i) {
        arrseen[i].value = arr[i];
        arrseen[i].seen = 0;
    }
    
    qsort(arrseen, NumCount, sizeof(struct arr_value), compar);
    
    struct arr_value *firstSame = arrseen;
    firstSame->first = firstSame;
    for(int i = 1; i < NumCount;   i) {
        if(arrseen[i].value != firstSame->value) {
            firstSame = arrseen   i;
        }
        arrseen[i].first = firstSame;
    }
    
    struct arr_value key;
    for(int i = 0; i < NumCount;   i) {
        key.value = arr[i];
        struct arr_value *found = (struct arr_value *)bsearch(&key, arrseen, NumCount, sizeof(struct arr_value), compar);
        struct arr_value *first = found->first;
        
        if(first->seen) {
            // value already seen, append to back
            arrResult[NumCount - 1 - resultCountBack] = first->value;
              resultCountBack;
        } else {
            // value is new, append
            arrResult[resultCount  ] = first->value;
            first->seen = 1;
        }
    }
    
    for(int i = 0; i < NumCount;   i) {
        printf("%d ", arrResult[i]);
    }

    return 0;
}

Output:

7 3 1 2 9 5 6 2 9 2 3 7

CodePudding user response：

1. To begin with, memmove doesn't run in a constant time, so the loop

    for (size_t i = 0; i < n - 1 - dupes_found;) 
    {
        if (newArr[i] == newArr[i   1])
        {
            dupes_found  ;
            int temp = newArr[i];
            memmove(&newArr[i], &newArr[i   1], sizeof(int) * (n - i - 1));
            newArr[n - 1] = temp;
        }
        else {
            i  ;
        }
    }
   

   drives the time complexity quadratic. You have to rethink the approach.

2. It seems that you are not using a crucial point:

   all the values in the arrays are positive

   It seriously hints that changing values to their negatives is a way to go.

   Specifically, as you iterate over the initial array, and bin-search its elements in temp, comparing the _ absolute values_. When an element is found in temp, and it is still positive there, flip all its dupes in temp to negative. Otherwise flip it in initial.

   So far, it is O(n log n).

   Then perform an algorithm known as stable_partition: all positives are moved in front of negatives, retaining the order. I must not spell it here - I don't want to deprive you of a joy figuring it out yourself (still O(n log n)

   And finally flip all negatives back to positives.