In situ hash algorithm
The in-situ hash algorithm is used to solve the problem with spatial complexity of O(1), and the result range is between [0, len (Num)], and num is the solution array provided by the problem.
The in-situ hash algorithm is mainly used in the array solution with the result range of [0, len (Num)]. The space complexity is limited. There is only one original array. The array element itself is taken as the subscript of num, that is, Num [num [i]], the element itself is stored in the subscript of the original array, and the value of the array itself is stored in the mark, which is solved by negative mark. The following is a summary of the leetcode topic.
Title Description:
Give you an unordered array of integers. Please find the smallest positive integer that does not appear in it. Example 1: input: [1,2,0] output: 3 Example 2: input: [3,4,-1,1] output: 2 Example 3: input: [7,8,9,11,12] output: 1 Tips: The time complexity of your algorithm should be O(n)，And only constant level extra space can be used. Related Topics array
Topic analysis:
The first thought is to use the hash table to store the elements in the array, and then traverse the integer from 1. The first number not in the hash table is our solution. We know to traverse from 1. What value does it reach?
Let the length of the array be n. if the elements in the array are exactly [1,..., n], the missing elements are n+1; What if there are numbers other than [1,..., n] in the array? Then the positions they occupy are the positions of the missing numbers in [1,..., n]. So the number we are looking for must be between [1,..., n+1]. So the maximum value we need to traverse is n+1.
The topic requires additional space at constant level, while we use hash table to store numbers. The space complexity is O(n), which does not meet the requirements. Based on this, we try to transform the original array into a hash table (the original array needs to be modified, so the title cannot ask that the original array cannot be modified), so no additional space is used.
We traverse the array. For the traversed value num, if its value is between [1, n], mark the number with index num-1 in the array. After traversal, if all positions are marked, the answer is n+1, otherwise it is the smallest unmarked position plus 1.
Since we only care about the numbers in [1, n], we can uniformly modify other numbers, such as changing to n+1, so that the numbers in the array are positive integers, which is also convenient for us to use the elements in the array as indexes.
/**
* Title: leetcode-41. Missing first positive number
*
* Give you an unordered array of integers. Please find the smallest positive integer that does not appear in it.
* Example 1:
* Input: [1,2,0]
* Output: 3
*
* Description: The time complexity is O(n) and the space complexity is O(1)
* No sorting, no additional data structures
* @author WZQ
* @version 1.0.0
* @date 2021/2/4
*/
public class Main41 {
/**
* In situ hash algorithm, array 0-n-1, the result must be between 1-n+1, and the result is index + 1
* @param nums
* @return
*/
public static int firstMissingPositive(int[] nums) {
if (nums == null || nums.length == 0){
return 1;
}
int n = nums.length;
// Negative filtering, n + 1 out of range
for (int i = 0; i < n; i++) {
if (nums[i] <= 0){
nums[i] = n + 1;
}
}
// Positive integer subscript i, marked num [num [i]] < 0
for (int i = 0; i < n; i++) {
// The element itself is guaranteed by absolute value
int num = Math.abs(nums[i]);
if (num <= n && nums[num - 1] > 0){
nums[num - 1] *= -1;
}
}
// A negative number indicates that the subscript has been accessed
for (int i = 0; i < n; i++) {
// Unmarked minimum
if (nums[i] > 0){
return i+1;
}
}
return n+1;
}
public static void main(String[] args) {
int[] arr = {3, 4, -1, 1};
System.out.println(firstMissingPositive(arr));
}
}
Other topics using in-situ hash:
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;
/**
* Title: 645. Wrong collection
* Description: In situ hash algorithm, optimizing spatial complexity O(1)
*
* Set S contains integers from 1 to n. Unfortunately, due to data errors, an element in the collection is copied
* The value of another element in the set causes the set to lose an integer and have a duplicate element.
* Given an array nums, it represents the result after the error of set S. Your task is to find the repeated integer first
* Find the missing integers and return them as an array.
*
* Example 1:
* Input: num = [1,2,2,4]
* Output: [2,3]
*
* The array nums with length n contains numbers [1, n], so it is obvious that the in-situ hash algorithm can be used.
* We traverse the array. For the traversed value num, we mark the number with index num-1 in the array,
* If it is found that a number has been marked in the traversal, it indicates that the number is a duplicate number.
* After the traversal, all the numbers are marked except the element at the corresponding position of the missing number.
*
* @author WZQ
* @version 1.0.0
* @date 2021/2/4
*/
public class Main645 {
// public int[] findErrorNums(int[] nums) {
// int[] result = new int[2];
// if (nums == null || nums.length <= 1){
// return result;
// }
//
// int length = nums.length;
//
// //The space complexity n can also be realized by counting the number of arrays
// Set<Integer> set = new HashSet<>();
// for (int i = 0; i < length; i++) {
// if (!set.contains(nums[i])){
// set.add(nums[i]);
// }else {
// result[0] = nums[i];
// }
// }
//
// for (int i = 1; i <= length; i++) {
// if (!set.contains(i)){
// result[1] = i;
// break;
// }
// }
//
// return result;
// }
/**
* optimization
* Space complexity O(1)
* @param nums
* @return
*/
public int[] findErrorNums(int[] nums) {
int[] result = new int[2];
if (nums == null || nums.length <= 1) {
return result;
}
int n = nums.length;
//In situ hash algorithm, spatial complexity O(1)
//sign
//The result is 1-n, corresponding to subscript 0-n-1
//If num [i] exists, mark num [num [i] - 1] as a negative number
//nums[i] stored in subscript
for (int i = 0; i < n; i++) {
//Get the original array object by absolute value
//Ensure that the value of the array is modified after traversal, and the original value can be obtained
int num = Math.abs(nums[i]);
if (nums[num - 1] > 0){
nums[num - 1] *= -1;
}else {
result[0] = num;
}
}
//Statistics, positive, that is, unmarked is missing
for (int i = 0; i < n; i++) {
if (nums[i] > 0){
result[1] = i+1;
}
}
return result;
}
}
/**
* Title: 287. Find duplicates
* Description:
*
* Given an array num containing n + 1 integers,
* The numbers are between 1 and n (including 1 and N),
* It can be seen that there is at least one duplicate integer.
* Find the number of repeated integers, assuming that there is only one repeated number of nums.
*
* @author WZQ
* @version 1.0.0
* @date 2021/2/4
*/
public class Main287 {
/**
* In situ hash, time complexity On, space complexity O1
* @param nums
* @return
*/
public static int findDuplicate(int[] nums) {
//The simplest is violence. The time complexity is O(n*n)
//Or use the array to count the number, and the space complexity is On
//In situ hash
int n = nums.length;
//Original array tag
for (int i = 0; i < n; i++) {
//Using negative numbers, the absolute value ensures that the original elements can be obtained by manipulating the data in other locations
int num = Math.abs(nums[i]);
//Negative mark
if (nums[num - 1] > 0) {
nums[num - 1] *= -1;
} else {
return num;
}
}
return 0;
}
}