Leetcode题解 - 12、数组问题 - 《算法》

283.LeetCode Move Zeros

1、创建辅助数组

class Solution {
    public void moveZeroes(int[] nums) {
        int [] newnums=new int[nums.length];
        int k=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                newnums[k++]=nums[i];
            }
        }
        for(int i=0;i<nums.length;i++){
            nums[i]=newnums[i];
        }
    }
}

2、直接在原来的数组上进行操作

class Solution {
    public void moveZeroes(int[] nums) {
        int k=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]!=0){
                nums[k++]=nums[i];
            }
        for(int i=k;i<nums.length;i++){
            nums[i]=0;
        }
    }
}

3、进行元素的交换

class Solution {
    public void moveZeroes(int[] nums) {
        int k=0;
        for(int i=0;i<nums.length;i++){
            int temp=0;
            if(nums[i]!=0){
                temp=nums[i];
                nums[i]=nums[k];
                nums[k]=temp;
                k++;
            }
        }
    }
}

26. 删除排序数组中的重复项

class Solution {
     public int removeDuplicates(int[] nums) {
        int k = 1;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[i-1]) {
                nums[k]=nums[i];
                k++;
            }
        }
        return k;
    }
}

基本思路： 1、遍历数组，当出现与前一个值不相等的情况时，进行k++操作以及数组赋值操作 2、关键点：在于处理时不出现角标越界的情况出现，我这里是默认不修改第一个值。 3、也可以通过while在操作，不使用for循环

80.删除排序数组中的重复项2

题目描述：给定一个增序排列数组 nums ，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。(不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。)

class Solution {
    public int removeDuplicates(int[] nums) {
        int k=1;
        int counts=1;
        for(int i=1;i<nums.length;i++){
            if(nums[i]!=nums[i-1]){
                nums[k++]=nums[i];
                counts=1;
            }else if(nums[i]==nums[i-1]&&counts<2){
                counts++;
                nums[k++]=nums[i]; //起始出错原因在于此处我虽然移动了看k，但是并未交换元素。
            }
        }
        return k;
    }
}

题解思路：
1、使用两个指针，i是遍历指针，指向当前遍历的元素；j指向下一个要覆盖元素的位置。
2、同样，我们使用count记录当前数字出现的次数。count的最小计数始终为1，至少出现1次。
3、为我们从索引1开始一次处理一个数组元素。
4、若当前元素与前一个元素相同，即nums[i]=nums[i-1]，则count++。若count>2，则说明遇到了多余的重复项。这种情况下只移动i，而不移动 j。
5、若 count <=2，则我们将 i 所指向的元素移动到 j 位置，并同时增加 i 和 j。
6、若当前元素与前一个元素不相同，即 nums[i] != nums[i - 1]，说明遇到了新元素，则我们更新count=1；并且将该元素移动到j位置，同时增加 i 和 j。
7、当遍历完成，则返回 j 。

75.颜色分类+

给定一个有n个元素的数组，数组中元素的取值只有0，1，2三种可能。为这个数组排序。
解决方法1:计数排序，统计0，1，2三个元素的个数。

class Solution {
    public void sortColors(int[] nums) {
        int[] count=new int[3];
        for(int i=0;i<nums.length;i++){
            count[nums[i]]++;
        }
        int index=0;
        for(int i=0;i<count[0];i++){
            nums[index++]=0;
        }
        for(int i=0;i<count[1];i++){
            nums[index++]=1;
        }
        for(int i=0;i<count[2];i++){
            nums[index++]=2;
        }
    }
}

解决方法2：三路快排思想

遍历元素，判断元素应该存储在哪一个区间中，然后进行移动下标、赋值元素的操作

class Solution {
    public void sortColors(int[] nums) {
        int n=nums.length;
        int l=0,index=0,r=n-1;    //l和r代表了两个边界条件
        while (index<=r){       //importment
            if(nums[index]==0){
                swap(nums,l,index);
                l++;
                index++;
            }else if(nums[index]==1){
                index++;
            }else {
                swap(nums,index,r);
                r--;
            }
        }
    }
    private void swap(int[] nums,int i,int j){
        int temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

注意遍历的截止条件

解决方法3：遍历赋值

class Solution {
    public void sortColors(int[] nums) {
        int num0 = 0;
        int num1 = 0;
        int num2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) {
                num2++;
                num1++;
                nums[num0++] = 0;
            } else if (nums[i] == 1) {
                num2++;
                nums[num1++] = 1;
            } else {
                nums[num2++] = 2;
            }
        }
    }
}

88. 合并两个有序数组

//给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
        int ai = m + n - 1;
        int mi = m - 1;
        int ni = n - 1;
        while (ni >= 0) {
            if (mi >= 0 && nums1[mi] > nums2[ni]) {
                nums1[ai--] = nums1[mi--];
            } else {
                nums1[ai--] = nums2[ni--];
            }
        }
    }
}

题解思路：（倒序处理） 1、题目给出了每个数组的实际有效长度，所以不要被后面的0所迷惑 2、数组1的有效长度为m，数组2的有效长度为n，所以其实真正有效的数组长度为m+n 3、因此我们只需要在nums数组长度为m+n的区间内操作即可，两数组的数进行比较，大的数放进数组 4、注意while和if中的边界条件

哪个数组赋值给长数组了，就移动哪一个。

215. 数组中的第K个最大元素

//在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
class Solution {
    public int findKthLargest(int[] nums, int k) {
        for (int i = 1; i < nums.length; i++) {
            int index = i - 1;
            int indexValue = nums[i];
            while (index >= 0 && indexValue < nums[index]) {
                nums[index + 1] = nums[index];
                index--;
            }
            nums[index + 1] = indexValue;
        }
        int index = nums.length - k + 1;
        return nums[index];
    }
}

此处使用插入排序算法，这道题主要就是考察排序算法，取第k个最大值无价值。