Remove Duplicate from Sorted Array/Slice

pub fn remove(i:&[isize]){
    if i.len()==0 {
        
    }

    let mut curr=i[0];
    let  index=0;
    let mut j=index;
    j+=1;
    i[j]=curr;
    for element in i.iter(){
        if curr!=i[element] {
            curr=i[element];
            i[j]=curr;
        }

    }
    println!("{:?}",i)
    
}

Hi rustaceans, please I'm trying to remove duplicate from a sorted array but I got error: the type [isize] cannot be indexed by &isize
the trait SliceIndex<[isize]> is not implemented for &isize
required because of the requirements on the impl of Index<&isize> for [isize]rustcE0277

underlying

 if curr!=**i[element]** {
            curr=**i[element**];
            i[j]=curr;
        }

First, what you want is Vec::dedup().

As for your code, I think what you want is for element in 0..i.len().

3 Likes

wow, thanks. This look easy, i don't even need to use slice. I can easily sort the vector ans use the other method to remove the duplicate. Oops, i still have a lot to read :slightly_smiling_face:

Your current code might run into a couple of problems

  1. i is immutable, so even if your algorithm functions as intended, it can't change the data in i
  2. using iter or a for loop iterates over the elements in the collection, you want the indices

Problem 1:

To index mutably and change elements like you have, you would need to change the signature to:

pub fn remove(i: &mut[isize])

Then, however, you wouldn't actually remove the elements – with a slice you could only replace them.

ProbIem 2:

When you call the method iter to iterate over the slice i:
for element in i.iter()
The type element is a reference to the items in the slice i – in other words, a reference to the isize elements in the slice.

Indexing

To index a slice (access its elements by their position, as you have done with [] notation) you must use a usize, so it does not make sense to use the element as an index. What you're doing is sort of like if you had typed:

let a = &['a', 'b', 'c'];
a['a'] // <- Instead of this you might want a[0]

Fix

@chrefr's answer is likely correct – You can use the dedup method, but you will need to create a Vec from the slice (the slice is just a reference to a contiguous memory region, the Vec is a contiguous region but it has control over the contents):

pub fn remove(i:&[isize]){
    let mut v = Vec::from_iter(i.iter().copied()); // copied was used to ensure v owns its data
    v.sort(); // if your data wasn't already sorted, you would need to do this for dedup to work properly
    v.dedup(); // you can also check out dedup_by and others
    println!("{:?}",v);
    println!("{:?}",i); // i has not changed!
    // you would probably want to do something like return v here, 
}

You might not even need a separate function for this option...

You can read more about what iter does and see that it iterates over references in the documentation here: slice - Rust

1 Like

Wow, thanks so concise :hugs:

There's another solution which doesn't require either a separate allocation, or a Vec to begin with: just move the duplicates to the end!

fn dedup<T: Eq>(slice: &mut [T]) -> (&mut [T], &mut [T]) {
    let len = slice.len();
    
    if len < 2 {
        return slice.split_at_mut(len);
    }

    let mut last_unique = 0;

    for next_candidate in 1..len {
        if slice[last_unique] != slice[next_candidate] {
            last_unique += 1;
            slice.swap(last_unique, next_candidate);
        }
    }

    slice.split_at_mut(last_unique + 1)
}

Edit: Apparently, the same algorithm will be in std (currently unstable) under the name partition_dedup().

4 Likes

Nice one, thanks. It really great there are many approaches. Gonna study this very well. It involves generics