Writing in the front
The blogger code xiaobai, this year to participate in the autumn recruitment, now began to brush questions, so write a blog to sort out records. Read the data structure in the sorting of the general content began to brush force deduction, this is the second problem encountered, is completely just began to learn the level of code, so many operations may be quite small, a lot of basic knowledge is not too understand. Please give us more advice.
1, the title
Example 1: input: nums1 = [1,2,2,1], nums2 = [2,2] output: [2,2] example 2: input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] output: [4,9] note: the number of occurrences of each element in the output should be the same as the minimum number of occurrences of the element in both arrays. We can ignore the order of the output.
2, train of thought
Assume that A = B =,2,14,5,7,6,1 [3] [1,3,5,3,21,3,2]
(1) Do not sort: define A pointer to the first element of A (for loop), which iterates through b, and copy the elements if they are equal. There is A problem: “The number of occurrences of each element in the output should be the same as the minimum number of occurrences of elements in both arrays.” If you go through b without limiting the number of occurrences it’s going to be A times b
(2) use the sort makes two arrays in order: first the bubbling, select, insert, and merge, quick sort, for AB the elements in the smallest, subsequent remove elements is the number of control back to the same without sorting method is more complex Bucket sorting: if only each element appears once is useful, same occurrences can’t control the count sorting: First, use two empty numbers CD to count AB, select the same index, compare the values of each position in CD, E stores the smaller value, and then remove the element in E
(3) Initial use counting sort! 1) How to control the index value of CD is the same, AB has different length and range: (Max -min+1); (Max -min+1); (Max -min+1); (Max -min+1); (Max -min+1); (Max -min+1); (Max -min+1)
3. Problems with the code and debugging process
3.1 code
class Solution { public int[] intersect(int[] nums1, int[] nums2) { int max1=nums1[0]; int min1=nums1[0]; int max2=nums2[0]; int min2=nums2[0]; max1 = getmax (max1,nums1); min1 = getmin(min1,nums1); max2 = getmax (max2,nums2); min2 = getmin(min2,nums2); int min = min1<min2? min1:min2; int max = max1>max2? max1:max2; int[] L1 = new int[max-min+1]; int[] L2 = new int[max-min+1];for(int i=0; i<nums1.length; i++){For (int num: nums1)
L1[nums1[i]-min]++;
}
for(int i=0; i<nums2.length; i++){ L2[nums2[i]-min]++; } int[] L = new int[max-min+1];for(int i=0; i<L.length; i++){ L[i]=L1[i]<L2[i]? L1[i]:L2[i]; } ArrayList<Integer> res = new ArrayList<>(); int index=0;for(int i=0; i<L.length; i++){while(L[i]>0){
res.add(i+min);
L[i]--;
}
}
int size= res.size();
// Integer[] res1 =res.toArray(new Integer [size]);
int[] res1 = res.stream().mapToInt(Integer::valueOf).toArray();
return res1;
}
public int getmax(int max ,int[] num){
for(int i=0; i<num.length; i++){if(num[i]>max){ max=num[i]; }}return (max);
}
public int getmin( int min,int[] num){
for(int i=0; i<num.length; i++){if(num[i]<min){ min=num[i]; }}return(min); }}Copy the code3.2 Debugging problems
(1) Index exceeds the limit
i<nums1.lengthRather thanL.lengthAdd: length is a string property, length () is an array method, size () is a List method
(2) Index is out of range
L[i]--
(3) Return array with 00
ArrayList<Integer> res = new ArrayList<>();
int index=0;
for(int i=0; i<L.length; i++){while(L[i]>0){ res.add(i+min); L[i]--; }}Copy the codeInt [] res1 = res.stream().mapToInt(Integer::valueOf).toarray (); or
int[] res1 = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
res[i] = res.get(i);
}
Copy the code2) Copy the first half of the array
return Arrays.copyOfRange(res,0,index)
Copy the codeYou can use one of these methods as the case may be, of course welcome to add, the owner of the building has just touched the code, all the knowledge here comes from the official solution of the force button and the topic comment section.
4. Understanding of official answers
The official method is to use hash table, because the hash table data structure has not looked at the concept, a simple check, set the key word key, the key function directly as the address to store data, is a kind of mapping. Nums1 = nums1; nums1 = nums1; nums1 = nums1; nums1 = nums1; Nums2 is then iterated over to retrieve the same element as the answer, and count–, then key and count are placed in the map, and when count is 0, the element is removed. Post to understand
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return intersect(nums2, nums1);The #intersect function returns the intersection of two arrays
The number of occurrences of the same element is 1. "The number of occurrences in the intersection set is equal to the minimum number of occurrences in both arrays."
# That's one step at a time. Java does not have this function.
# suddenly realize this is a call in its own right this step is to iterate over the shorter array ！！！！ That's wonderful.
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();Create a hash table, similar to a two-dimensional array, one for the key value, one for the number of occurrences
for (int num : nums1) {Use a flag num to traverse nums1
int count = map.getOrDefault(num, 0) + 1;#getOrDefault: If num exists in the map, use its value
Num = 0; num = 0; Get returns the mapped value of num
map.put(num, count);# put num and count into the map, set a breakpoint here, see the result on the right
}
int[] intersection = new int[nums1.length];Create an array to store the results
int index = 0;#index to control the storage of elements in the result array
for (int num : nums2) {
int count = map.getOrDefault(num, 0);# The number of occurrences of the same element is read from the map
if (count > 0) {
intersection[index++] = num;# have the same element, output
count--;#count--
if (count > 0) {
Add num and count to map
map.put(num, count);
} else{ map.remove(num); }}}return Arrays.copyOfRange(intersection, 0, index);# copy the elements in the array 0<= I }}Copy the code5, to optimize
If the array is already sorted, how do I optimize the algorithm
What’s so convenient about sorting? Convenient statistics of the number of occurrences, from left to right. If s1[I]=s2[j], the elements should be recorded and moved right at the same time if they are equal, or smaller if they are not. s1[i]
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
int i = 0;
int j = 0;
int L1 = nums1.length;
int L2 = nums2.length;
ArrayList<Integer> res=new ArrayList<>();
while (i<L1&&j<L2){
if (nums1[i]==nums2[j]){
res.add(nums1[i]);
i++;
j++;
}
if (nums1[i]<nums2[j]){
Index out of bound error: else if
i++;
}
if (nums1[i]>nums2[j]){
j++;
}
}
int[] res1=res.stream().mapToInt(Integer::valueOf).toArray();
returnres1; }}Copy the codeError:
Official code:
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
Arrays.sort(nums1);Sort the array
Arrays.sort(nums2);
int length1 = nums1.length, length2 = nums2.length;
int[] intersection = new int[Math.min(length1, length2)];
int index1 = 0, index2 = 0, index = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else{ intersection[index] = nums1[index1]; index1++; index2++; index++; }}returnArrays.copyOfRange(intersection, 0, index); }}Copy the code6 summarizes
The above is all content, if you can finish reading, thank you for your time, we have any questions or improvement advice, or what brush experience, you can exchange more. Brush questions make people happy, hope to grow up quickly.