Arrays 101

[hotpineapple]

가장 긴 연속한 1의 길이 찾기

1. 아이디어
   • 배열을 순회하며 1인경우 +1, 0인 경우 최대값 업데이트 후 0으로 초기화
2. 코드

   class Solution {
   public int findMaxConsecutiveOnes(int[] nums) {
       int cnt = 0, max = 0;
       for (int i=0; i<nums.length; i++) {
           if (nums[i]==1) cnt++;
           else {
               max = Math.max(max,cnt);
               cnt = 0;
           }
       }
       return Math.max(max,cnt);
   }
   }

[hotpineapple]

Find Numbers with Even Number of Digits

1. 아이디어
   • Integer.toString 메서드 활용

2. 코드

   class Solution {
   public int findNumbers(int[] nums) {
       int cnt = 0;
       for (int i=0;i<nums.length;i++) {
           int len = Integer.toString(nums[i]).length();
           if (len %2 ==0) cnt++;
       }
   
       return cnt;
   }
   }

[hotpineapple]

Squares of a Sorted Array

O(n) 풀이

1. 아이디어
   • 인풋 배열이 정렬되어 있는 점, 음수로 크더라도 제곱하면 큰 값을 가진다는 점에서 착안하여, 양 끝(투 포인터)만 비교하며 배열을 한번만 순회

2. 코드

   class Solution {
   public int[] sortedSquares(int[] nums) {
       int len = nums.length;
       int l = 0;
       int r = len - 1;
       int[] res = new int[len];
       for (int i = len - 1; i >= 0; i--) {
           if (Math.abs(nums[l]) > Math.abs(nums[r])) {
               res[i] = (int) Math.pow(nums[l], 2);
               l++;
           } else {
               res[i] = (int) Math.pow(nums[r], 2);
               r--;
           }
       }
   
       return res;
   }
   }

   • 번외 (Arrays.sort() 를 이용하지 않고 TreeMap을 활용하여 정렬하였습니다)

     class Solution {
     public int[] sortedSquares(int[] nums) {
     Map<Integer,Integer> map = new TreeMap<>(); 
     for (int i=0;i<nums.length;i++) {
         int square = (int)(Math.pow(nums[i],2));
         int cnt = map.getOrDefault(square,0);
         map.put(square,cnt+1);
     }
     
     int[] res = new int[nums.length];
     int i=0;
     for (Integer key : map.keySet()) {
         int cnt = map.get(key);
         for(int j=0;j<cnt;j++) res[i++] = key;
     }
     
     return res;
     }
     }

[hotpineapple]

Duplicate Zeros

• in-place

  class Solution {
  public void duplicateZeros(int[] arr) {
      for (int i=0;i<arr.length-1;i++) {
          if(arr[i]==0) {
              for (int j=arr.length-1;j>i+1;j--) {
                  arr[j] = arr[j-1];
              }
              arr[i+1] = 0;
              i++;
          }
      }
  
  }
  }

[hotpineapple]

Merge sorted array (beats 100%)

1. 아이디어
   • 두 인풋 배열이 정렬된 상태임을 활용하여 맨 앞부터 각 한 개의 원소끼리만 비교 (병합정렬의 sort 단계와 같다)
2. 코드

   class Solution {
   public void merge(int[] nums1, int m, int[] nums2, int n) {
       int i=0,j=0;
       int[] res = new int[nums1.length];
       for (int k=0;k<m+n;k++) {
           if(i<m && j<n ){
               if(nums1[i]<nums2[j]) {
                   res[k] = nums1[i]; 
                   i++;
               }else {
                  res[k] = nums2[j]; 
                   j++;
               }
           }else if(j<n){
               while(j<n){ 
                   res[k++]=nums2[j++];
               }
               break;
           }else if(i<m){
               while(i<m){
                   res[k++]=nums1[i++];
               }
               break;
           }
       }
       for(int k=0;k<nums1.length;k++){
           nums1[k] = res[k];
       }
   }
   }

[hotpineapple]

Remove element

class Solution {
    public int removeElement(int[] nums, int val) {
        int cnt = 0;
        int len = nums.length;
        int k = len-1;
        for (int i = 0; i < len; i++){
            if(nums[i] == val) {
                cnt++;
                for(int j = k; j > i;j--) {
                    if (nums[j] != val) {
                        nums[i] = nums[j];
                        k = j - 1;
                        break;
                    }
                }
            }
        }

        return len-cnt;
    }
}

[hotpineapple]

Check If N and Its Double Exist

class Solution {
    public boolean checkIfExist(int[] arr) {
        for (int i=0;i<arr.length;i++) {
            for (int j=0;j<arr.length;j++) {
                if (i==j) continue;
                else if (arr[i]==2*arr[j]) return true;
            } 
        }
        return false;
    }
}

[hotpineapple]

Replace Elements with Greatest Element on Right Side

1. 아이디어
   • 범위별 max 값을 미리 계산하여 시간복잡도 O(n)

2. 코드

   class Solution {
   public int[] replaceElements(int[] arr) {
       int[] max = new int[arr.length];
       max[arr.length-1] = arr[arr.length-1];
       for(int i=arr.length-2;i>=0;i--) {
           max[i] = Math.max(arr[i],max[i+1]);
       }
   
       for (int i=0;i<arr.length-1;i++) {
           arr[i] =max[i+1];
       }
       arr[arr.length-1]=-1;
       return arr;
   }
   }

[0tak2]

이번에만 PR을 봐주세요 😅

https://github.com/sonic247897/2024_algorithm_study/pull/2/files