leetcode [#27]

目录

• 1. 题目
• 2. 解决方案
• 3. 注意事项

题目

Given an array and a value, remove all instances of that value in place and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Example:
Given input array nums = [3,2,2,3], val = 3

Your function should return length = 2, with the first two elements of nums being 2.

---

解决方案

public class Solution {
    public int removeElement(int[] nums, int val) {
        int N = nums.length;
        Arrays.sort(nums);
        int equal = 0;
        for(int k = 0; k < N; k++){
            if(nums[k] == val) {
                equal++;
            }
        }
        int result = N - equal;
        if(equal == N) return 0;
        for(int h = 0; h < N; h++){
            if(nums[h] == val) {
                if(h < result) {
                    for(int m = 0; m < result; m++){
                        if(h + equal + m < N){
                            nums[h + m] = nums[h + equal + m];
                        }
                    }
                }
                break;
            }
        }
        return result;
    }
}

---

注意事项

1. 要求不能开辟新的数组，使用常量空间原地完成。
2. 先对数组排序，并统计出要删除元素的个数。
3. 之后的工作就是进行遍历，并对某些位置元素进行移动。当equal == N，表明数组中全部元素都要删除，可以直接返回0。
4. 当第一个待删除元素的下标大于新数组长度result，不需任何操作（指移动元素）；否则，从第一个待删除元素的下标开始，将间隔（待删除元素个数equal）的元素依次移动到当前位置，注意不要数组越界。