Tag: 原地算法

Posted 2022-04-20Updated 2022-04-20LeetCode / Medium / 复习2 minutes read (About 258 words)

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

当前数字之外的积等于左边所有数字的积乘以右边所有数字的积。
因此可以维护两个数组，分别计算从左到右的乘积，和从右到左的乘积。

由于返回答案不算占用空间，因此可以将左侧乘积的数组保存在答案数组上。
然后在遍历时，从右至左遍历，使用一个变量储存右边的乘积，直接将两者的乘积更新在答案数组上。
此时空间复杂度为O(1)。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        ans[0] = 1;
        
        for(int i = 1; i < nums.length; i++){
            ans[i] = ans[i-1] * nums[i-1];
        }
        
        int rightProduct = 1;
        
        for(int j = nums.length-1; j >=0; j--){
            ans[j] = ans[j] * rightProduct;
            rightProduct *= nums[j];
        }
        return ans;   
    }
}

Posted 2022-04-18Updated 2022-08-30LeetCode / Medium / 复习3 minutes read (About 505 words)

48. Rotate Image

Question

You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Solution 1

此方法是in-place算法。

visited[][]数组记录访问情况，遍历所有位置，如果已访问则跳过。
循环替换矩阵上的每一个位置，如果已经访问过则break。
如果未访问则将要替换位置的值保存，并且在visited[][]数组上记录。
然后继续遍历替换过的位置。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] visited = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(visited[i][j] == 1) continue;
                int x = i, y = j;
                int value = matrix[i][j];
                while(true){
                    int s = n-1-x, t = y;
                    if(visited[t][s] == 1) break;
                    int temp = matrix[t][s];
                    matrix[t][s] = value;
                    value = temp;
                    visited[t][s] = 1;
                    x = t;
                    y = s;
                }
            }
        }
    }
}

Solution 2

此方法类似Solution 1，但是并非原地算法。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] mat = new int[m][n];
        
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int s = n-1-i, t = j;
                mat[t][s] = matrix[i][j];
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                matrix[i][j] = mat[i][j];
            }
        }
    }
}

Solution 3

辅助方法getPixel计算旋转后的像素位置。
旋转时候矩阵内的四个分区的像素会互相替换。
因此需要将需要旋转的初始位置记录进入队列。
旋转图像时根据getPixel方法计算出需要替换的位置。
然后依次替换像素。

Code

class Solution {
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        Queue<Integer> queue = new LinkedList();
        for (int p = 0; p < n/2; p++){
            for(int q = 0; q < (n+1)/2; q++){
                queue.offer(p * n + q);
            }
        }

        while(!queue.isEmpty()){
            int i = queue.poll();
            int INDEX = i;
            boolean flag = true;
            int temp = matrix[i/n][i%n];
            while(i != INDEX || flag ){
                flag = false;
                int j = getPixel(n, i);
                int swap = matrix[j / n][j % n];
                matrix[j / n][j % n] = temp; 
                temp = swap;
                i = j;
            }
        }     
    }
    
    private int getPixel(int n, int o){
        int row = o / n;
        int col = o % n;
        int newRow = col;
        int newCol = n - (row + 1);
        return (newRow * n) + newCol;
    }
}

Posted 2022-04-17Updated 2022-04-17LeetCode / Medium / 复习2 minutes read (About 295 words)

75. Sort Colors

Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white, and blue.

We will use the integers 0, 1, and 2 to represent the color red, white, and blue, respectively.

You must solve this problem without using the library’s sort function.

快速排序是原地排序，因此此问题可以采用快速排序解决。

选择left上的元素pivot，设置一个指针index为left+1。
遍历left+1至right的数组，如果遍历的值小于pivot则将nums[i]与nums[index]交换，然后将index向右移动。

因此index左侧的元素均小于pivot，index右侧的元素均大于pivot。
最后将nums[index]与pivot交换，此时pivot左侧元素均小于它，右侧元素均大于它，因此index不需要再动。
然后分别向下递归left至index-1，index+1至right。

class Solution {
    public void sortColors(int[] nums) {
        quickSort(nums, 0, nums.length-1);
    }
    
    private void quickSort(int[] nums, int left, int right){
        if( right - left < 1 ){
            return;
        }
        int pivot = nums[left];
        int index = left+1;
        for(int i = index; i <= right; i++){
            if(nums[i] < pivot){
                int temp = nums[index];
                nums[index] = nums[i];
                nums[i] = temp;
                index++;
            }
        }
        index--;
        
        nums[left] = nums[index];
        nums[index] = pivot;
        
        quickSort(nums,left,index-1);
        quickSort(nums,index+1,right);
    }
}

Posted 2022-04-03Updated 2022-05-02LeetCode / Easya minute read (About 187 words)

88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order.

The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

采用双指针，从结尾开始遍历两个数组。
比较后按倒叙插入第一个数组。

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1 , j = n - 1, k = m + n - 1;
        
        while ( i >= 0 && j >= 0 ) {
            if ( nums1[i] < nums2[j] ){
                nums1[k] = nums2[j];
                j--;
                k--;
            }               
            else {
                nums1[k] = nums1[i];
                i--;
                k--;
            }
        }
        if ( i < 0 ){
            while ( j >= 0 ){
                nums1[k] = nums2[j];
                j--;
                k--;
            }
        }
    }
}

Question

Solution 1

Code

Solution 2

Code

Solution 3

Code

Recents

Archives

Links