What is a "loop invariant"? - Moment For Technology

Summary of knowledge:

A cyclic invariant is a property that remains constant during the course of the cycle;
What stays the same is what we define according to the task and the purpose, different loop invariants correspond to different algorithms;
I like to write loop invariants as comments in my code to help clarify the thinking of the code.

Example 1: “force button” Problem 26: Remove duplicates from sorted arrays (simple)

Given a sorted array, you need to remove repeated elements in place, so that each element appears only once, and return the new length of the removed array.

Example 1:

Given the array nums = [1,1,2], the function should return the new length 2, and the first two elements of the original array NUMs are changed to 1,2. You don't have to worry about elements beyond the new length of the array.Copy the code

Example 2:

Given nums = [0,0,1,1,1,2,2,3,3,4], the function should return the new length 5, and the first five elements of the original array NUMs are modified to 0,1, 2,3, 4. You don't have to worry about elements beyond the new length of the array.Copy the code

Important conditions: sort arrays;
Requirement: Repeat elements can occur at most once.
Train of thought:
- Using loop variablesiIterate over the input array once;
- usejOverwrite the input array.Pay attention to: The values of elements whose subscript difference is 1 cannot be equal.
conclusion:iTraverse,jThe assignment,j - 1Compare.

Reference code 1:

public class Solution {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return len;
        }

        // Loop invariant: nums[0..j) has no repeating elements
        // j refers to the next element to be assigned
        int j = 1;
        for (int i = 1; i < len; i++) {
            if(nums[i] ! = nums[j -1]) { nums[j] = nums[i]; j++; }}returnj; }}Copy the code

Reference code 2:

public class Solution {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return len;
        }
        // Loop invariant: nums[0..j] has no duplicate element, j is the subscript of the element just assigned
        int j = 0;
        for (int i = 1; i < len; i++) {
            if (nums[i] != nums[j]) {
                j++;
                nums[j] = nums[i];
            }
        }
        return j + 1; }}Copy the code

Example 2: “Force button” Problem 283: Move zero (easy)

Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12] output: [1,3,12,0,0]Copy the code

Description:

You must operate on the original array; you cannot copy additional arrays.
Minimize the number of operations.

Reference code 1:

public class Solution {

    public void moveZeroes(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        // nums[0..j) != 0
        // nums[j..i) == 0
        int j = 0;
        for (int i = 0; i < len; i++) {
            if(nums[i] ! =0) { nums[j] = nums[i]; j++; }}for (int i = j; i < len; i++) {
            nums[i] = 0; }}}Copy the code

class Solution:

    Given an array nums, write a function that moves all zeros to the end of the array while preserving the relative order of the non-zero elements.
    # Quicksort method, the simplest, most direct

    def moveZeroes(self, nums) :
        """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """

        # keep loop invariants [0, j] non-zero,
        [j, len-1] = 0
        # j indicates the position of the next non-zero element
        j = 0

        for i in range(len(nums)):
            # pass 0, not 0 exchange to the front
            ifnums[i] ! =0:
                nums[j], nums[i] = nums[i], nums[j]
                j += 1
Copy the code

Reference code 2:

public class Solution {

    public void moveZeroes(int[] nums) {
        int len = nums.length;
        if (len < 2) {
            return;
        }

        // Loop invariant: nums[0..j] is nonzero, and the order is kept, with j pointing to the element to be assigned
        // nums(j.. i) = 0
        int j = -1;
        for (int i = 0; i < len; i++) {
            if(nums[i] ! =0) { j++; nums[j] = nums[i]; }}for (int i = j + 1; i < len; i++) {
            nums[i] = 0; }}}Copy the code

Problem 27: Moving elements (simple)

Given an array nums and a value val, you need to remove all elements equal to val in place, and return the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so using O(1)O(1)O(1) extra space.

The order of the elements can be changed. You don’t have to worry about elements beyond the new length of the array.

Example 1:

Given nums = [3, 2, 2, 3], val = 3, the function should return the new length 2, and the first two elements in nums are both 2. You don't have to worry about elements beyond the new length of the array.Copy the code

Example 2:

Given nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2, the function should return the new length 5, and the first five elements in nums are 0, 1, 3, 0, 4. Note that these five elements can be in any order. You don't have to worry about elements beyond the new length of the array.Copy the code

Description:

Why is the return value an integer, but the output answer an array?

Note that the input array is passed as a “reference,” which means that changes to the input array in the function are visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. Int len = removeElement(nums, val); // Modifying the input array in the function is visible to the caller. // Depending on the length your function returns, it prints out all the elements in the array within that length range. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Set a pointer to j. If you encounter an element to be deleted, skip to the next element to be deleted. If you encounter a reserved element, assign a value to j, and j index + 1.

Reference code 1:

public class Solution {

    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        // nums[0..j] does not contain val, j refers to the position of the next element to be assigned
        // If it is equal to val, it skips; if it is not equal to val, it assigns
        int j = 0;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                nums[j] = nums[i];
                j++;
            }
        }
        returnj; }}Copy the code

class Solution:
    def removeElement(self, nums, val) :
        """ :type nums: List[int] :type val: int :rtype: int """

        size = len(nums)
        if size == 0:
            return 0

        j = 0
        for i in range(size):
            ifnums[i] ! = val: nums[j] = nums[i] j +=1
        return j
Copy the code

Reference code 2:

public class Solution {

    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }

        // nums[0..j] does not contain val, j refers to the value of the element just assigned
        // val = val
        // assign when val is not equal to val
        int j = -1;
        for (int i = 0; i < len; i++) {
            if (nums[i] != val) {
                j++;
                nums[j] = nums[i];
            }
        }
        return j + 1; }}Copy the code

Example 4: “Force button” Problem 80: Remove duplicate item II (medium) from sort array

Given an incrementally ordered array nums, you need to remove the repeated elements in place, so that each element appears at most twice, and return the new length of the removed array.

Instead of using extra array space, you must modify the input array in place and do so using O(1) extra space.

Description:

Why is the return value an integer, but the output answer an array?

Note that the input array is passed as a “reference,” which means that changes to the input array in the function are visible to the caller.

You can imagine the internal operation as follows:

// Nums is passed by reference. Int len = removeDuplicates(nums) // Modifying the input array in the function is visible to the caller. // Depending on the length your function returns, it prints out all the elements in the array within that length range. for (int i = 0; i < len; i++) { print(nums[i]); }Copy the code

Example 1:

Input: nums = [1,1,1,2,2,3] Output: 5, nums = [1,1,2,2,3] Explanation: The function should return the new length length = 5, and the first five elements of the original array are changed to 1,1,2,2,3. You don't have to worry about elements beyond the new length of the array.Copy the code

Example 2:

Input: nums =,0,1,1,1,1,2,3,3 [0] output: 7, nums =,0,1,1,2,3,3 [0] interpretation: The function should return the new length = 7, and the first five elements of the original array have been modified to 0, 0, 1, 1, 2, 3, 3. You don't have to worry about elements beyond the new length of the array.Copy the code

Tip:

0 <= nums.length <= 3 * 104
-10^4 <= nums[i] <= 10^4
numsIn ascending order

Key: Two numbers whose subscript difference is 2 cannot be the same. The value of the element to be assigned can be assigned as long as it is different from the value of the element to the left of it.

The loop invariant: nums[0..j) is an ordered array, and the same element appears up to 222 times, with j pointing to the next element to be assigned.

Reference code 1:

public class Solution {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return len;
        }

        // Loop invariant: nums[0..j) is the array that is finally returned
        // During initialization, the first two bits are valid
        // [0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 4]
        // j
        // i
        // j points to the next element to be filled in
        int j = 2;
        for (int i = 2; i < len; i++) {
            if(nums[i] ! = nums[j -2]) { nums[j] = nums[i]; j++; }}returnj; }}Copy the code

from typing import List


class Solution:
    def removeDuplicates(self, nums: List[int]) - >int:
        size = len(nums)
        if size <= 2:
            return size
        # counter indicates the next subscript to be overridden
        counter = 2
        # Numbers with subscripts 0 and 1 are always preserved, so the traversal starts at subscript 2
        for i in range(2, size):
            ifnums[i] ! = nums[counter -2]:
                nums[counter] = nums[i]
                counter += 1
        return counter
Copy the code

class Solution(object) :
    def removeDuplicates(self, nums) :
        """ :type nums: List[int] :rtype: int """
        l = len(nums)
        if l <= 2:
            return l
        counter = 2
        for i in range(2, l):
            ifnums[i] ! = nums[counter -2]:
                nums[counter] = nums[i]
                counter += 1
        return counter
Copy the code

Reference code 2:

public class Solution {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len < 3) {
            return len;
        }
        
        // Loop invariant: nums[0..j] j refers to the last element that has been assigned
        int j = 1;
        for (int i = 2; i < len; i++) {
            if(nums[i] ! = nums[j -1]) { j++; nums[j] = nums[i]; }}return j + 1; }}Copy the code

Complexity analysis:

Time complexity: O(N)O(N)O(N), we iterate through each array element once;
Space complexity: O(1)O(1)O(1).

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

What is a “loop invariant”?

Example 1: “force button” Problem 26: Remove duplicates from sorted arrays (simple)

Example 2: “Force button” Problem 283: Move zero (easy)

Problem 27: Moving elements (simple)

Example 4: “Force button” Problem 80: Remove duplicate item II (medium) from sort array

What is a “loop invariant”?

Example 1: “force button” Problem 26: Remove duplicates from sorted arrays (simple)

Example 2: “Force button” Problem 283: Move zero (easy)

Problem 27: Moving elements (simple)

Example 4: “Force button” Problem 80: Remove duplicate item II (medium) from sort array

Related Posts

Have a problem how to Debug, remote service can also control | Java Debug notes

【Java】 about static code block execution order, so simple a question, should everyone know?

MySQL > add primary key void problem