Arrays-chapter6

Height Checker

자꾸 단순 구현으로 풀려고 하넼ㅋㅋㅋ(32.12%, 16.85%)

import java.util.*;
class Solution {
    public int heightChecker(int[] heights) {
        int result= 0;
        int[] expected = new int[heights.length];
        
        for(int i = 0;i<heights.length;i++){
            expected[i] = heights[i];
        }
        Arrays.sort(expected);
        for(int i = 0; i<expected.length;i++){
            if(heights[i] != expected[i]){
                result++;
            }
        }
       return result; 
    }
}

배열 복사 이런 식으로도 가능한 듯

int[] expected = heights.clone();

 

2번째 방법 ( 86.55$, 39mb)

class Solution {
    public int heightChecker(int[] a) {
        int[] freq = new int[101]; //length of array should be 101 as indexes will go from 0 to 100
        int n = a.length;
        
        //fill the frequency of each array input
        for(int i =0;i<n;i++)
            freq[a[i]]++;
        
        //freq array values will go from 1 to 100(as mentioned in the question)
        //arrayPointer will go from 0 to n-1 (normal array traversal)
        //ans is the total no. of elements that are mismatched
        int freqVal =1, arrayPtr=0;
        int ans =0; 
        
        while(arrayPtr<n){
            //if particular element exist in the array then it's frequency will be greater than 0. 
            //only then consider it else ignore and move to next element in freq array
            
            //check if the array element value and frequency value match 
            //and acordingly increment ans
            
            //also increment the array pointer and reduce frequency by 1 
       
            if(freq[freqVal] >0){
                if(a[arrayPtr]!=freqVal) ans++;
                arrayPtr++;
                freq[freqVal]--;
            }
            //element not present in array. move to next
            else {
                freqVal++;
            }
            
        }
        
        return ans;
    }
}

 

 

Third Maximum Number

: There are 3 ways.

1. After sorting , find the 3rd distinct maximum number

2. Creating 3 variables, keep comparing.

 

 

(94.84%, 46.91%)

import java.util.*;

//first way
class Solution {
    public int thirdMax(int[] nums) {
        int nextMax = Integer.MAX_VALUE;
        int count = 0;
        Arrays.sort(nums); 
        for(int i = nums.length-1;i>=0;i--){
            if(nums[i] < nextMax) {
                count++;
                nextMax = nums[i];
            }
            if(count==3){
                return nextMax;
            }
        }
        return nums[nums.length-1];
    }
}

//second way

class Solution {
    public int thirdMax(int[] nums) {
        
        boolean minIsMin = true;
        int flag = 0;
        int first = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        int third = Integer.MIN_VALUE;
        for(int i : nums){

            if(i > first){
                flag++;
                third = second;
                second = first;
                first = i;
            }
            else if (i > second && i < first){
                flag++;
                third = second;
                second = i;
               
            }
            else if (i > third && i < second ) {
                
                flag++;
                third = i;
            }
            else if(i == Integer.MIN_VALUE && minIsMin){
                flag++;
                minIsMin = false;
            }
            
        }
        
        return flag < 3 ? first : third;
    }
}

 

 

Find All Numbers Disappeared in an Array **** 다시 풀어보는게 좋을 듯

: 이상한 게, Arrays.asList().contains를 사용할 수 없다.

사용해도 값을 포함하고 있어도 false로 나와서 시도해보다가 관뒀음ㅜㅜ

 

set을 사용해서 하는 방법도 있다.

 

접근방식이 독특하다.

내가 생각하지 못할 방법일 듯

import java.util.*;
class Solution {
    public List<Integer> findDisappearedNumbers(int[] nums) {
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            // nums[n - 1] = n;  //can not do this, since you will override the origin node.
            int idx = Math.abs(nums[i]) - 1;
            if (nums[idx] > 0) nums[idx] = - nums[idx];
        }
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) res.add(i + 1);
        }
        return res;
    }
}

 

Squares of a Sorted Array

 

1. First way(15.05%, 53.9MB)

Arrays.sort ->O(nlogn)

import java.util.*;
class Solution {
    public int[] sortedSquares(int[] nums) {
        
        for(int i = 0; i<nums.length;i++){
            nums[i] = nums[i] * nums[i];
        }
        Arrays.sort(nums);
        return nums;
    }
}

2. Second way

: Originally, it was sorted in non-decreasing order.

 투포인터 방식으로 절대값의 순서를 변경한 뒤, 제곱

class Solution {
    public int[] sortedSquares(int[] nums) {
        int left=0, right=nums.length-1;
        int pos=nums.length-1;        
        int[] ans = new int[nums.length];
        
        while(left<=right)
        {
            if(Math.abs(nums[left])>Math.abs(nums[right]))
            {
                ans[pos]=nums[left]*nums[left];
                left++;
            }
            else
            {
                ans[pos]=nums[right]*nums[right];
                right--;
            }
            pos--;
        }
            return ans;
    }
}