从数组中删除特定整数的最后一个匹配项

Question

由于某种原因，我的解决方案并不完整。我从隐藏的规格测试中得到了80/100。

1. 我的解决方案有什么问题？可能有一个我没有想到的用例
2. 使用ArrayList而不是array会如何改变空间/时间复杂性
3. 有没有更好的方法来解决这个问题

我当前的解决方案处理：

• 空输入数组

编写一个Java方法，它从给定的整数元素数组arr中删除给定整数元素x的最后一个匹配项。

该方法应返回一个新数组，其中包含给定数组arr中的所有元素，除了元素x的最后一次出现。其余元素应在输入和返回的数组中以相同的顺序出现。

右边的代码向您展示了一个代码框架，其中仍然缺少一个静态方法的实现。提供这个实现并通过自己编写更多测试或使用提供的测试和规范测试来检查它是否正确。

class RemoveLastOccurrenceArray {

    /**
     * Takes the array and the last occurring element x,
     * shifting the rest of the elements left. I.e.
     * [1, 4, 7, 9], with x=7 would result in:
     * [1, 4, 9].
     *
     * @param x   the entry to remove from the array
     * @param arr to remove an entry from
     * @return the updated array, without the last occurrence of x
     */
    public static int[] removeLastOccurrence(int x, int[] arr) {

        // if arr == null return null;
        if (arr == null || arr.length == 0) return arr;

        // return a new array which will be size arr.legnth-1
        int[] res = new int[arr.length - 1];

        // introduce an int tracker which keep tracks of the index of the last occurrence of x
        int last_index = -1;

        // traverse through the array to get the index of the last occurrence
        for (int i = 0; i < arr.length; i++) if (arr[i] == x) last_index = i;

        int i = 0, j = 0;

        // copying elements of array from the old one to the new one except last_index
        while (i < arr.length) {
            if (i == last_index) {
                if (i++ < res.length) {
                    res[j++] = arr[i++];
                }
            } else res[j++] = arr[i++];
        }

        // if we pass in x which is not in the array just return the original array
        if (last_index == -1) return arr;

        // are there duplicates in the array? - WORKS
        // does the array have negative numbers? - WORKS
        // Is the array sorted/unsorted - WORKS

        return res;
    }
}

import static org.junit.Assert.*;

import org.junit.*;

public class RemoveLastOccurrenceArrayTest {
    @Test
    public void testRemoveArray_Empty() {
        int[] array = new int[0];
        assertEquals(0, RemoveLastOccurrenceArray.removeLastOccurrence(5, array).length);
    }

    @Test
    public void testFirstSimple() {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] result = {2, 3, 4, 5, 6, 7, 8, 9, 10};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(1, input));
    }

    @Test
    public void testLastSimple() {
        int[] input = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
        int[] result = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(10, input));
    }

    @Test
    public void testPositiveInMiddleDuplicate() {
        int[] input = {1, 2, 3, 3, 4, 5};
        int[] result = {1, 2, 3, 4, 5};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(3, input));
    }

    @Test
    public void testNegativeFirst() {
        int[] input = {-3, -1, 2, -3, 3, 4, 5, 0};
        int[] result = {-3, -1, 2, 3, 4, 5, 0};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(-3, input));
    }

    @Test
    public void testLasttoRemove() {
        int[] input = {1, 4, 7, 9};
        int[] result = {1, 4, 7};
        assertArrayEquals(result, RemoveLastOccurrenceArray.removeLastOccurrence(9, input));
    }
}

Answer 1

这就是答案非常感谢！

此外，如果没有x可供查找，则您的x将崩溃。。。我的不是。也许那就是20马克去的地方？

我已经在检查这个，但在我的代码中为时已晚。所以我不得不搬家

if（last_index==-1）返回arr 在while循环之前，我得到了100分。

你的教授喜欢这个吗？换一种方式，我认为没有比你的答案更有效的了。但也许他们喜欢看到使用的java类。。。

你的教授没有告诉你在哪里丢了分数吗？如果他们不告诉你他们期望满分是多少，你就无法提高。但这是另一种方式。。。再说一次，在我看来没有更好，也不值得再加二十分。我会把它贴出来，因为这是另一种方式

    public int[] removeLastOccurrence2(int x, int[] arr) {

        // if arr == null return null;
        if (arr == null || arr.length == 0) return arr;

        // Fill an ArrayList with your initial array ...

        java.util.List list = new java.util.ArrayList(arr.length);

        for (int i=0; i<arr.length; i++) {
            list.add(arr[i]);
        }

        int[] res;

        // Now ... use ArrayList methods to do the work.

        // Also, if there is no x to find, yours crashes ... mine doesn't.
        // Maybe that's where the twenty marks went?

        if ( list.lastIndexOf(x) != -1 ) { // This screens for no x found at all ...

             list.remove( list.lastIndexOf(x) ); // Done!

             // Make a new array to return.
             res = new int[list.size()];
             for (int i=0; i<list.size(); i++) {
                 res[i] = (int) list.get(i);
             }

        } else {

            // No 'x' found, so just return the original array.
            res = arr;
        }        

       return res;
    }

Answer 2

为什么不尝试反向迭代？

for(int i = arr.length; i => 0; i--)
{ 
   if (arr[i] == x)
   {
       return ArrayUtils.remove(arr, i)
    }
}

然后，找到索引后，您可以使用Apache Commons ArrayUtils删除命令删除