Is there a way to copy int[] to another int[] without repeated ints?

Question

We can't use ArrayList or something like that, because the teacher told us to not use them, so I got stuck at this point. The signature of the function is:

public static int[] deleteNth(int[] elements, int maxOccurrences){}

I already go down over the array and get the lenght for the copied int result[] that i will return but now i got stucked thinking how i can paste certain elements. I wrote the I/O of the method:

deleteNth(new int[] {20,37,20,21}, 1) // return [20,37,21]
deleteNth(new int[] {1,1,3,3,7,2,2,2,2}, 3) // return [1, 1, 3, 3, 7, 2, 2, 2]

In a last chance for me, i try something like this but my brains burn out

for(int n:result) {
 int n1=0;
 boolean nope=false;
 for(;n1<elements.length;) {
  //TODOthings
 }
 result[n]=elements[n1];
} 

For those people who don't believe me, here's my code:

public static int[] deleteNth(int[] elements, int maxOccurrences) {
        int[] result = null;
        if (elements != null && maxOccurrences > 0) {
            int result_lenght=elements.length;
            int ocurrences=0;
            for(int n:elements) {
                for(int n1:elements) {
                    if(n==n1 && ocurrences!=maxOccurrences) {
                        ocurrences++;
                        result_lenght--;
                    }
                }
            }
            result=new int[result_lenght];
            for(int n:result) {
                int n1=0;
                boolean nope=false;
                for(;n1<elements.length;) {
                    //todothings
                }
                result[n]=elements[n1];
            }
        }else {
            result=elements;
        }
        return result;
    }

Answer 1

What about the following algorithm, it is maybe not the fastest (roughtly (n^2)/2) but really simple with litle and easy code:

• Create a flag array to mark the elements to delete
• Parse for all elements to delete and mark them
• Create a new result array the right length based on the count of elements to delete
• Copy all elements while skiping the ones flaged as to be removed

Code:

int[] original = {1, 1, 3, 4, 3, 3, 3, 6, 3, 5, 3};  // Our array to clean

System.out.print("Processing: ");
for(int i = 0; i < original.length; i++) System.out.print(original[i] + " ");
System.out.println();

int[] flags = new int[original.length];     // Flags to indicate where we delete
  
int max = 3;    // Lets say max 3 occurences
int del = 0;    // Count deletions

// Parse all elements
for(int idx=0; idx < original.length; idx++)
{
    // Initialize occurence counter
    int occurences = 0;

    // Scan up to current position and mark all occurences over limit
    // Note: stop ad idx, so to limit test by factor 2)
    for (int cidx=0; cidx <= idx; cidx++)
    {
        if (original[cidx] == original[idx])
        {
            occurences++;
            
            if (occurences > max && flags[cidx] == 0)
            {
                flags[cidx] = 1;
                del++;
            }
        }
    }
}

System.out.print("Flags: ");
for(int i = 0; i < flags.length; i++) System.out.print(flags[i] + " ");
System.out.println();

// Create final array
int[] final_array = new int[original.length - del];

// Get values not flagged
int pos = 0;
for(int idx=0; idx < original.length; idx++)
{
    if (flags[idx] == 0)
    {
        final_array[pos] = original[idx];
        pos++;
    }
}

System.out.print("Result: ");
for(int i = 0; i < final_array.length; i++) System.out.print(final_array[i] + " ");
System.out.println();

Results:

Processing: 1 1 3 4 3 3 3 6 3 5 3
Flags: 0 0 0 0 0 0 1 0 1 0 1 
Result: 1 1 3 4 3 3 6 5

Answer 2

Since no library facilities such as Set or Map and appropriate implementations is allowed to be used in this task and re-inventing the wheels of re-implementing these classes seems to be far more complicated than necessary, a simple solution could be based on using object wrapper Integer for int to use null to mark values that should be deleted.

So the algorithm would be as follows:

1. Convert input int[] to Integer[]
2. Initialize nullCount, Using nested loops, found the duplicate values exceeding the treshold and set them to null along with increasing nullCount
3. Create result array, copy non-null values and return it.

Example implementation:

public static int[] deleteNth(int[] elements, int maxOccurrences) {
    Integer[] arr = new Integer[elements.length];
    int i = 0;
    for (Integer x : elements) {
        arr[i++] = x;
    }
    
    int nullCount = 0;
    for (i = 0; i < arr.length; i++) {
        Integer x = arr[i];
        if (null == x) {
            continue;
        }
        int cnt = 1;
        for (int j = i + 1; j < arr.length; j++) {
            Integer y = arr[j];
            if (null == y) {
                continue;
            }
            if (x.equals(y)) {
                cnt++;
                if (cnt > maxOccurrences) {
                    arr[j] = null;
                    nullCount++;
                }
            }
        }
    }
    int[] result = new int[arr.length - nullCount];
    i = 0;
    for (int j = 0; j < arr.length; j++) {
        Integer x = arr[j];
        if (null != x) {
            result[i++] = x;
        }
    }
    return result;
}

Test and output:

System.out.println(Arrays.toString(deleteNth(new int[] {20,37,20,21}, 1))); // return [20,37,21]
System.out.println(Arrays.toString(deleteNth(new int[] {1,1,3,3,7,2,2,2,2}, 3))); // return [1, 1, 3, 3, 7, 2, 2, 2]

Output:

[20, 37, 21]
[1, 1, 3, 3, 7, 2, 2, 2]

---

A faster version could use additional boolean array to track repeated values so that they could be skipped in the nested loop.

---

A stream-based solution (just for reference and comparison) would be like this:

• prepare initial map with array elements as keys, and value - list of indexes using Collectors.groupingBy
• remap entries in the initial map: index -> key (array element) using flatMap and Stream::limit to abide by threshold
• sort the new entries by index
• retrieve the values and collect them to array

public static int[] deleteNth(int[] arr, int threshold) {
    return IntStream
            .range(0, arr.length)
            .boxed()
            .collect(Collectors.groupingBy(
                i -> arr[i], 
                Collectors.mapping(i -> i, Collectors.toList())
            ))
            .entrySet()
            .stream()
            .flatMap(e -> e.getValue().stream()
                    .limit(threshold)
                    .map(ix -> Map.entry(ix, e.getKey())) // Map.entry since Java 9
            )
            .sorted(Map.Entry.comparingByKey())
            .mapToInt(Map.Entry::getValue)
            .toArray();
}

Answer 3

You can do this with the help of a HashMap to keep track of the number of occurences of each number:

public static int[] deleteNth(int[] elements, int maxOccurrences){
    // get number of occurrences of each number in elements less than max
    Map<Integer,Integer> occurences = new HashMap<>();
    for(int element : elements) {
        int count = occurences.containsKey(element) ? occurences.get(element) : 0;
        if(count < maxOccurrences) occurences.put(element, count+1);
    }
    // calculate total size of array to return
    int size = 0;
    for(int numberOccurences : occurences.values()) size += numberOccurences;
    int[] res = new int[size];
    // clear map to reuse it
    occurences.clear();
    // reiterate over elements array
    int i = 0;
    for(int element : elements) {
        int count = occurences.containsKey(element) ? occurences.get(element) : 0;
        // add number to resulting array if its count in it is still less than max
        if(count < maxOccurrences) res[i++] = element;
        occurences.put(element, count+1);
    }
    return res;
}

Answer 4

A possible straightforward solution (albeit inefficient) would be to start by creating a method that accepts as parameter an array, the number of elements on it, and a value, and returns the number of times that the value appears in the array, something like:

int total_occurences(int[] elements, int size, int value) 

Use that method in your main code:

int copy[] = new int [elements.length];
int elements_copied = 0;
for(int i = 0; i < elements.length; i++) {
    // Check if you are "allowed" to copy the element
    if(total_occurences(copy, elements_copied , value <= maxOccurrences){
      copy[elements_copied] = element[i];
      elements_copied ++;
    }          
}
// copy the content to a new array of size = elements_copied
// return that array

The main idea is to first create an array (i.e., int copy[] = new int [elements.length]) with the same size as the array elements, since you do not beforehand how many duplicates there are. Iterate over the array elements, and for the current element (i.e., element[i]) check if we already have a copied (that element) the maximum number allowed (i.e., maxOccurrences):

if(total_occurences(copy, elements_copied , value <= maxOccurrences)

if not copy the element and increment the number of elements copied so far:

 copy[elements_copied] = element[i];
 elements_copied ++;

We need to use a different variable to iterate over the copy array because it might contain a different number of elements than the array elements. For instance, after a duplicated number has been "removed". In the end, you can create a new array (the one to be returned) with a size equals to the variable elements_copied, and copy the elements from the copy array into this newly created array. In this way, you will return an array without missing values at the end of it.