1. Numbers that appear more than half of the time in the array
There is a number in the array that occurs more than half of the length of the array, please find this number.
You can assume that arrays are non-empty and that there is always a majority of elements in a given array.
Example 1:
Input: [1, 2, 3, 2, 2, 2, 5, 4, 2]
output: 2
Jianzhi Offer 39. Numbers that appear more than half of the time in the array
1.1 Sorting
Since the title stipulates that the number of occurrences of numbers exceeds half the length of the array, it only needs to be sorted, and then the element in the middle is the response result.
There are many sorting methods, such as bubbling, quick sorting and so on.
Tried using bubble sort, but it’s running out of time.
Quick row.
public int majorityElement(int[] nums) {<!-- -->
quickSort(nums,0,nums.length-1);
return nums[nums. length/2];
}
public void quickSort(int [] nums,int low,int high){<!-- -->
if(high <= low) return;
int partition = partition(nums,low,high);
quickSort(nums,low,partition-1);
quickSort(nums, partition + 1, high);
}
public int partition(int [] nums,int low,int high){<!-- -->
int part = nums[low];
int left = low;
int right = high;
while(left<right){<!-- -->
while(left<right & amp; & amp; nums[right] > part){<!-- -->
right--;
}
nums[left] = nums[right];
while(left<right & amp; & amp; nums[left] <= part){<!-- -->
left ++ ;
}
nums[right] = nums[left];
}
nums[left]= part;
return left;
}
I tried using quick sort, thinking it would at least improve the speed, but obviously, the performance is not high.
Using Arrays.sort()
Seems a little better.
1.2 map
To unify the number of occurrences of an element, use hashmap, set the element to k, and set the number of occurrences to value. When the number of occurrences is greater than half the length of the array, the element can be found. And it only needs to be traversed once.
public int majorityElement(int[] nums) {<!-- -->
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums. length;i ++ ){<!-- -->
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
if(map.get(nums[i]) > nums.length/2){<!-- -->
return nums[i];
}
}
return 0;
}
Time complexity: O(n), unavoidable need to traverse the array once
Space complexity: O(n), using a hash table to store
However, the effect in terms of time is still not obvious. In the loop, it is still necessary to judge whether the elements in the hash table meet the requirements.
1.3 Voting algorithm
The main idea is to use two variables, one result stores the number of the array, and the other time stores the number of occurrences, and judges whether the current number is the same as the subsequent number. If they are the same, then the number will be increased by one. If not, the number will be reduced by 1 until The last number becomes 0, which means that it is definitely not the result, and then result points to the next element, which must be an element. After the number is added or subtracted, it is greater than or equal to = 1 (subject condition), then this number is returned.
The above is a bit confusing, for example [1, 2, 3, 2, 2, 2, 5, 4, 2]
public int majorityElement(int[] nums) {<!-- -->
int count = 0;
Integer result = null;
for(int num:nums){<!-- -->
if(count == 0){<!-- -->
result = num;
}
count +=(num==result)?1:-1;
}
return result;
}
Time complexity: O(n)
Space complexity: O(1)
2. Number appears only once
number that occurs only once
Given a non-empty integer array nums , each element appears twice except for a certain element that appears only once. Find the element that appears only once.
You must design and implement an algorithm of linear time complexity to solve this problem that uses only constant extra space.
Example 1:
Input: nums = [2,2,1]
Output: 1
2.1 HashSet
The main function of hashset is to deduplicate. I just need to judge whether this number has appeared before. If it appears, then remove this element, and the last thing left is the desired result.
public int singleNumber(int[] nums) {<!-- -->
HashSet<Integer> hashSet = new HashSet<>();
for(int i=0;i<nums. length;i ++ ){<!-- -->
if(!hashSet.contains(nums[i])){<!-- -->
hashSet.add(nums[i]);
}else{<!-- -->
hashSet. remove(nums[i]);
}
}
return hashSet.toArray(new Integer[hashSet.size()])[0];
}
Time complexity: O(n) traversing the linked list, converted to an array time complexity O(m);
Space complexity: O(m) the number of unique elements, but since there will only be one, the complexity is O(1);
2.2 XOR
XOR characteristics:
0^ a= a;
a^a=0;
a^b ^ a =b
The condition of the title is that only two other elements will appear, and the offset will be exactly 0 after the two times.
public int singleNumber(int[] nums) {<!-- -->
int flag = 0;
for(int num: nums){<!-- -->
flag^=num;
}
return flag;
}
Time complexity: O(n)
Space complexity: O(1)
3 refers to Offer 03. Repeated numbers in the array
Sword Finger Offer 03. Repeated numbers in the array
All numbers in an array nums of length n are in the range 0 to n-1. Some numbers in the array are repeated, but I don’t know how many numbers are repeated, and I don’t know how many times each number is repeated. Please find any repeated numbers in the array.
enter:
[2, 3, 1, 0, 2, 5, 3]
Output: 2 or 3
3.1 Using HashMap
The traversal stores the elements in the hash table. If the number of times is greater than 1, it means that there are duplicate elements, and the elements can be returned directly. The specific approach is similar to the first question. Hashsets can also be used.
public int findRepeatNumber(int[] nums) {<!-- -->
HashMap<Integer,Integer> map = new HashMap<>();
for(int i=0;i<nums. length;i ++ ){<!-- -->
map.put(nums[i],map.getOrDefault(nums[i],0) + 1);
if(map.get(nums[i]) >1){<!-- -->
return nums[i];
}
}
return 0;
}
Time complexity: O(n)
Space complexity: O(n)
3.2 In-place exchange
In the title condition, it means that the value of the array element is between 0-n-1. You only need to sort the elements according to the corresponding subscripts. If the first subscript has a repeated value, then it is a repeated element.
public int findRepeatNumber(int[] nums) {<!-- -->
int i = 0;
while(i<nums. length){<!-- -->
if(nums[i] == i){<!-- -->
i + + ;
continue;
}
if(nums[nums[i]] == nums[i]) return nums[i];
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
return -1;
}
Time complexity: O(n)
Space complexity: O(1)
3. Color classification (Dutch flag)
sort by color
Given an array nums of n elements red, white, and blue, sort them in-place so that elements of the same color are next to each other in the order red, white, and blue.
We use the integers 0, 1, and 2 to represent red, white, and blue, respectively.
This has to be solved without using the library’s built-in sort function.
3.1 Bubble sort + double pointer
The main idea is still bubbling, but the 0 element is placed on the far left first, and then the 0 elements are all over. At this time, the left subscript is the starting position of 1, and then 1 is exchanged with 2 again.
public void sortColors(int[] nums) {<!-- -->
int left = 0;
// First swap all 0 to the left
for (int right = 0; right < nums. length; right ++ ) {<!-- -->
if(nums[right] == 0 ){<!-- -->
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
left ++ ;
}
}
// Exchange all 1 to the left of 2, here must first + +, because the left is still 0 element at this time
for(int right = left ;right<nums. length; + + right){<!-- -->
if(nums[right] == 1){<!-- -->
int temp = nums[right];
nums[right] = nums[left];
nums[left] = temp;
+ + left;
}
}
}
Time complexity: O(n*2)
Space Complexity: O(1)
4.2 Multi-pointer one-time traversal
First of all, there must be two pointers, one pointing to the beginning and the other pointing to the end, but a pointer is needed to move and exchange positions. Left is equivalent to locking the position of 0, and right is locking the position of 2.
public void sortColors(int[] nums) {<!-- -->
int left = 0;
int right = nums. length -1;
int index = 0;
while(index <= right){<!-- -->
if(nums[index] == 0){<!-- -->
swap(nums,index++,left++);
}else if(nums[index] == 2){<!-- -->
swap(nums,index,right--);
}else{<!-- -->
index + + ;
}
}
}
public void swap(int [] nums,int i,int j){<!-- -->
int temp = nums[i];
nums[i]=nums[j];
nums[j]=temp;
}
Time complexity: O(n)
Space Complexity: O(1)
Summary
For problems such as arrays, it is generally sorting, moving, and repeating such problems.