Leetcode exercise - in-place remove without clone

help
1

Hi,

So I was just trying to resolve some leetcode exercises and I got myself using the "hail-mary" clone call on a vector.

My question is: Is there a way to build a enumerated iterator without cloning nums vector?

    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        let mut pivot: i32 = nums[0];
        let mut occ: usize = 0;
        let mut rm_count: usize = 0;
        let nums_orig_size: usize = nums.len();
        // TODO how do I avoid a clone here?
        for (i, num) in nums.clone().iter().enumerate() {
            if *num != pivot {
                pivot = *num;
                occ = 1;
            } else {
                occ += 1;
            }
            if occ > 2 {
                nums.remove(i - rm_count);
                rm_count += 1;
            }
        }
        (nums_orig_size - rm_count) as i32
    }
2

I suggest iterating over indexes rather than iterating over the elements.

To improve performance you could also try taking advantage of swap_remove, if you don't need to preserve the original order of the elements.

3

Vec uses unsafe in its retain and dedup_by implementation to allow itself to temporarily have a "hole" in the Vec's data.

In safe code, Rust doesn't allow breaking unique ownership or having uninitialized memory, so every element in a vector or slice must be valid at all times. It also must stay valid in case any function panics and interrupts the loop.

For safe code there's vec.swap_remove, vec.swap, and std::mem::swap, std::mem::replace that help moving data in slices without invalidating the items.

4

ty @jumpnbrownweasel and @kornel for the explanations and suggestions!

5

If you coerce to a slice of Cell as outlined in this article, you can keep keep an index to a target cell to write to while iterating over the rest of the slice.

2 Likes
6

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.