Leetcode records - sort -215, 347, 451, 75

215. No K Big element

Ideas

【 The final position 】 Find the second in the array K Big element , Related to sorting , Quick row can find the final position of an element in the sorted array every time （ And the left ones are smaller than this number , The ones on the right are larger than this number ）, Learn from the idea of fast platoon , Optimize the search process with subscripts . Find the final position of one element at a time , If it is equal to K-1, Return this element to ; otherwise , If the element position is less than K, On its right side, the sub array is arranged quickly , Otherwise, line up quickly on the left .

Code

public int findKthLargest0(int[] nums, int k){
    
        int left=0,right=nums.length-1;
        while(left<right){
    
            int mid=findIndex(nums,left,right); // Calling this method has sorted an element （mid It's about 
            if (mid==nums.length-k) return nums[mid]; // When mid Is the indicated subscript 
            else if (mid>nums.length-k) //mid Keep to the right , Go to the left 
                right=mid-1;
           else
               left=mid+1;
        }
        return nums[left];
    }
    public int findIndex(int[] nums,int begin,int end){
     // The specified interval will begin The final position of the subscript element is found 
        int value=nums[begin];
        int left=begin;
        int right=end;
        while(left<right){
    
            while (left<right&&nums[right]>value)
                right--;
            while(left<right&&nums[left]<=value)
                left++;
            int temp=nums[left];
            nums[left]=nums[right];
            nums[right]=temp;
        }
        nums[begin]=nums[left];
        nums[left]=value;
        return left;
    }

347. front K High frequency elements

Ideas

【 Element frequency order 】 Because the number of different elements is statistically sorted , Learn from bucket sorting , First count the number of elements （HashMap）, Then put the same number of elements into a bucket （ A two-dimensional List）, Elements output from more to less .

Code

class Solution {
    
    public int[] topKFrequent(int[] nums, int k) {
    
        // Count the number of elements related or an attribute of an element —— use HashMap Key value pair 
        // Integer is not good as subscript , Just use the number as the subscript 

        // initialization HashMap
        Map<Integer,Integer> map=new HashMap<>();// Keys represent numbers , Value represents the number of occurrences 
        for (int key:nums){
    
            // Whether to include the key , If there is no initialization value 1
            if (map.containsKey(key))
                map.put(key,map.get(key)+1);
            else
                map.put(key,1);
        }
        // Put the same number of times in one List in 
        List<Integer>[] list=new ArrayList[nums.length+1];// In case they are all the same elements , At this time, it should be placed in the subscript nums.length It's about 
        for (int key:map.keySet()){
     // For each key ——map.keySet() Get key collection 
            int value=map.get(key); // Get the value of this key , Indicates the number of key digits 
            if(list[value] == null){
    
                list[value] = new ArrayList();
            }

            list[value].add(key); // Add it to the subscript of the corresponding number 
        }
        // Reverse traversal List Output —— Because every child list I don't know how many , use int[] Ergodic , So again list Of addAll
        List<Integer> output=new ArrayList<>();
        for (int i = nums.length; i >0 && output.size()<k; i--) {
    
            if (list[i]==null) continue;;
            output.addAll(list[i]);
        }
        return output.stream().mapToInt(Integer::valueOf).toArray();
    }
}

451. Sort the characters according to their frequency of occurrence

Ideas

【 Element frequency order 】 It is still the element frequency / Number related topics , And the scope is unknown , It's not about the following three elements , Learn from bucket sorting . Count the number of occurrences of each character , Then fill the bucket according to the number , Finally, take in reverse order .

Code

1. And 347 Similar version

class Solution {
    
    public String frequencySort(String s) {
    
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
    
            if (map.get(s.charAt(i))==null) map.put(s.charAt(i),1);
            else map.put(s.charAt(i),map.get(s.charAt(i))+1);
        }
        List<Character>[] list=new ArrayList[s.length()+1]; // Be careful 
        for (Character key:map.keySet()){
    
            int value=map.get(key);
            if (list[value]==null) list[value]=new ArrayList<>();
            list[value].add(key);
        }
        List<Character> listOut=new ArrayList<>();
        for (int i = list.length-1; i >0 ; i--) {
    
            if (list[i]==null) continue; // Be careful 
            for (int j = 0; j < list[i].size(); j++) {
    
                for (int k = 0; k < i; k++) {
    
                    listOut.add(list[i].get(j));
                }
            }
        }
        StringBuilder str = new StringBuilder();
        for (Character character : listOut) {
    //  Yes ArrayList Traversal , Put a character in StringBuilder in 
            str.append(character);
        }
        return str.toString();
    }
}

2. List Save characters , Arrange according to the number of occurrences of each character from small to large , Finally, output in reverse order （ because List After the storage and weight removal , So take map Inside value, Output value Characters ）

class Solution {
    
    public String frequencySort(String s) {
    
        Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
    
            if (map.get(s.charAt(i))==null) map.put(s.charAt(i),1);
            else map.put(s.charAt(i),map.get(s.charAt(i))+1);
        }
        List<Character> listOut = new ArrayList<Character>(map.keySet());
        Collections.sort(listOut, (a, b) -> map.get(b) - map.get(a));
        StringBuilder str = new StringBuilder();
        int size = listOut.size();
        for (int i = 0; i < size; i++) {
    
            char c = listOut.get(i);
            int frequency = map.get(c);
            for (int j = 0; j < frequency; j++) {
    
                str.append(c);
            }
        }
        return str.toString();
    }
}

75. Color classification

Ideas

【3 The elements are sorted as a whole 】 If you use the method of occurrence frequency of multiple elements above , It's a little bit of a hassle . Three elements can be encountered 0 Move forward , encounter 2 Move back , encounter 1 unchanged . Use a double fingered needle （ One left Point to the sorted 0 Next person , One right Point to the sorted 2 Last ）, At the same time, one more pointer i Traversal elements in turn , Meet the conditions and exchange with the corresponding pointer elements , Then take different steps . Special , If right Exchange ends ,i I don't know what elements are exchanged , Cannot step directly , Need to be handled again i, and right normal –.

Code

class Solution {
    
    public void sortColors(int[] nums){
    
        // The left and right pointers point to be placed 0 Location and waiting 2 The location of ;i Step through elements , See if you can exchange —— Thought is 0 Put it in the front ,2 Put it back 
        int left=0,right=nums.length-1,i=0;
        while(i<=right){
     // Be careful right It's all in the back 2, No need to deal with it ,right Can be any value at , Need to deal with , If 0, You need to change to the front 
            if (nums[i]==0)
                swap(nums,i++,left++);
            else if (nums[i]==2)
                swap(nums,i,right--); // In the back is 2, It's possible to change the front 0/1/2, Need to be handled again 
            else
                i++;
        }
    }
    public void swap(int[] nums,int index1,int index2){
    
        int temp=nums[index1];
        nums[index1]=nums[index2];
        nums[index2]=temp;
    }
}

Skill summary

Sorting related ideas

① The position of an element / The watershed —— Refer to quick platoon （ Quick row put one element in the final position at a time , And the left side is small , Big on the right ）
② The number of multiple elements is related —— Reference bucket sorting （ According to the number of elements, put them into the corresponding bucket ）
③ The three elements are sorted —— One is put in front , One is put back , One does not deal with

Statistics of the number of elements HashMap

Map<Character,Integer> map=new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
    
            if (map.get(s.charAt(i))==null) map.put(s.charAt(i),1);
            else map.put(s.charAt(i),map.get(s.charAt(i))+1);
        }

List relevant （ A two-dimensional List,Integer Of List Turn array ）

① When List Specify the length , And every element is stored List（ A two-dimensional List）：

List<Integer>[] list=new ArrayList[nums.length+1];// In case they are all the same elements , At this time, it should be placed in the subscript nums.length It's about 
        for (int key:map.keySet()){
     // For each key ——map.keySet() Get key collection 
            int value=map.get(key); // Get the value of this key , Indicates the number of key digits 
            if(list[value] == null){
    
                list[value] = new ArrayList();
            }

            list[value].add(key); // Add it to the subscript of the corresponding number 
        }

② A two-dimensional List Each of the List The first time you use it, you should declare ：if (list[value]==null) list[value]=new ArrayList<>();
③ List Add many key value pairs addAll：output.addAll(list[i]); list[i] For one List.
④ Integer Type of List Turn array ：return output.stream().mapToInt(Integer::valueOf).toArray();

map operation （ keyset 、 Key sequence 、 A key value +1）

① Get key collection ：map.keySet(), Generally used to traverse each key：for (int key:map.keySet()){}, You can also directly create a List：List<Character> listOut = new ArrayList<Character>(map.keySet());.
② The value of a key +：map.put(s.charAt(i),map.get(s.charAt(i))+1);
③ according to map Inside value Sort key （ There is List in ）：Collections.sort(listOut, (a, b) -> map.get(b) - map.get(a));

character List turn String（Character Arrays are the same thing ）

StringBuilder str = new StringBuilder();
for (Character character : listOut) {
    //  Yes ArrayList Traversal , Put a character in StringBuilder in 
    str.append(character);
}
return str.toString();