Member Avatar for steveballinger

I'm trying to write a function that takes an array of unsorted positive integers N elements long.

The function should return the same array (no new allocations) with all duplicated integers replaced with -1 and moved to the end of the array.

So for example, the string:


1136788999

becomes ...

136789-1-1-1-1

Does anyone have a code snippet that accomplishes this? Sounds like a hash table could be the best approach here, but not sure.

Thanks much in advance!

~Steve

  • 3 Contributors
  • 8 Replies
  • 124 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by steveballinger

Dani AI

Generated

This is an in-place transformation: keep the first occurrence of each 1-digit value and move any later copies to the end as -1. was on the right track with a tiny "seen" tracker, and 's hash-table idea works too but is heavier than needed for a 0–9 domain. Repeatedly shifting the tail on each duplicate (the common naive approach) costs O(n^2) in the worst case — avoid it.

A simple, fast alternative is a single left-to-right pass with a write index plus a constant-size seen mask. Write unseen values to a[write++] and mark them as seen; skip seen values. After the scan, fill the remaining slots with -1. That preserves the order of first occurrences and runs in O(n) time using O(1) extra space.

Example implementation (C#-style):

void CompactKeepFirst(int[] a) {
    int seen = 0;
    int w = 0;
    for (int i = 0; i < a.Length; i++) {
        int v = a[i];
        int bit = 1 << v;           // safe because v is 0..9
        if ((seen & bit) == 0) {
            seen |= bit;
            a[w++] = v;
        }
    }
    for (int i = w; i < a.Length; i++) a[i] = -1;
}

Notes and edge cases: this relies on values being small nonnegative digits and that -1 is a free sentinel. If values can be outside 0..9 or -1 may appear in input, either choose a different sentinel or use a HashSet<int> (allocates) for general integers. If preserving original order is not required and allocations are banned, an in-place sort then compaction is another option but it changes element order. Test with arrays that are all unique, all identical, and mixed duplicates to confirm behavior.

Recommended Answers

All 8 Replies

Member Avatar for Member #46692

I'm trying to write a function that takes an array of unsorted positive integers N elements long.

The function should return the same array (no new allocations) with all duplicated integers replaced with -1 and moved to the end of the array.

So for example, the string:


1136788999

becomes ...

136789-1-1-1-1

Does anyone have a code snippet that accomplishes this? Sounds like a hash table could be the best approach here, but not sure.

Thanks much in advance!

~Steve

Yeah I'd agree with that. Go with the hasttable.

Member Avatar for steveballinger

Yeah I'd agree with that. Go with the hasttable.

Thank you. I'm a bit new at this and having trouble getting started. So for the example given, how would you start? Very much obliged.

Member Avatar for lok_tan

Before that, please confirm. What is the input parameter of the function? is it an array of integers? or a string?
since you mention that the function must return the same array (no allocation), meaning that the input parameter is also an array.
but in your example, you mention it about a string.


Regards,

Lok

Member Avatar for steveballinger

Sorry. I misspoke. It is an array.

Member Avatar for lok_tan

Sorry, forgot to asking.. is all the integers are 1-digit (0 to 9)?

regards,

Lok

Member Avatar for steveballinger

Yes. All are 1-digits.

Member Avatar for lok_tan

Easy then, no need to use any hashtable, just use array of boolean.

private bool[] flag = new bool[10];

each time you iterate the integer array, check against the flag array using the current integer value as it's index. if the flag[integer[loop_index]] == false, leave it as it is, then change it to true.
but if it's already true, meaning the integer value already exists, so shift the integer array contents by -1, started from the already exists integer value, and replace the last integer-array value with -1.

Hope that logic will help.

Regards,

Lok

Member Avatar for steveballinger

That is easier and terrific advice. I'll give that a try. Thanks so much!

~Steve

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.