reverse-array-solution

Solve Reverse Array with the best solution

Reverse Array là bài toán phổ biến mà bất cứ kĩ sư phần mềm nào cũng cần phải hiểu rõ và áp dụng thành thục. Mở rộng ra cho cả string và các bài toán khác.

Cùng tìm hiểu một số lời giải cơ bản cho Array ngay thôi nào!

1. Reverse Array với ESTCV Approach

Làm việc với Array tất nhiên phải chú ý tới complexity (độ phức tạp). Arrays provide O(1) lookup by index (Tìm kiếm theo index trên Array luôn có độ phức tạp nhỏ nhất O(1)

Ngoài đảo ngược Array, cũng có một bài toán khác khá hay liên quan tới Array là duplicate item trong array.

Given an array of numbers, replace each even number with two of the same number. e.g, [1,2,5,6,8] -> [1,2,2,5,6,6,8,8]

Cho một danh sách các mảng, thay thế mỗi số chẵn bằng 2 số.
  • Time Complexity: O(n) aka linear time
  • Space Complexity: O(1) aka constant space

Độ phức tạp về thời gian là O(n) do duyệt mảng từ đầu tới cuối

package com.src;

public class Main {
    public static void main(String[] args) {
      // Mảng input sẽ có -1 đại diện cho index sẽ duplicate bằng số chẵn
        int[] a = new int[]{2, 4, 1, 0, 3, -1, -1, -1};
        cloneEvenNumber(a);
        for (int item : a) {
            System.out.println(item);
        }
    }

    public static int[] cloneEvenNumber(int[] a) {
        if (a == null || a.length == 0) {
            return a;
        }
        int end = a.length;
        int i = getLastNumber(a);
        while (i >= 0) {
            // Mảng chạy từ phải qua trái
            if (a[i] % 2 == 0) {
                a[--end] = a[i];
            }
            // Set vào phía sau mảng nếu là số lẻ, lặp nếu là số chẵn
            a[--end] = a[i];
            i--;
        }
        return a;
    }

  	// Tìm vị trí i cuối cùng không phải là -1
    public static int getLastNumber(int[] a) {
        int i = a.length - 1;
        while (i >= 0 && a[i] == -1) {
            i--;
        }
        return i;
    }
}

2. Traverse từ Both Ends

Reverse Array

1) Initialize start and end indexes as start = 0, end = n-1
2) Swap arr[start] with arr[end]
3) Recursively call reverse for rest of the array.

Về ý tưởng cơ bản thì khi muốn đảo ngược array, ta sẽ thực hiện đổi chỗ tuần tự phần tử đầu và cuối. Tiến dần về trong cho tới phần tử ở giữa. Có thể hiện thực code như sau:

package com.src;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[]{3, 4, 2, 7, 1};
        reverse(a);
        for (int item : a) {
            System.out.println(item);
        }
    }

    public static void reverse(int[] a) {
        int start = 0;
        int end = a.length - 1;
        while (start < end) {
            swap(a, start, end);
            start++;
            end--;
        }
    }

    private static void swap(int[] a, int start, int end) {
        int temp = a[start];
        a[start] = a[end];
        a[end] = temp;
    }
}

3. Traverse String

Bài toán đảo ngược không những áp dụng cho Array mà còn có thể áp dụng cho String. Cho dãy string “This is Kieblog”, đảo ngược chuỗi với Time Complexity và Space Complexity là O(n)

package com.src;

public class Main {
    public static void main(String[] args) {
        System.out.println(reverseWord("This is Kieblog"));
    }

    public static String reverseWord(String s) {
        StringBuilder builder = new StringBuilder();
        int currentWordEnd = s.length();

        for (int i = s.length() - 1; i >= 0; i--) {
          // Thêm space nếu có
            if (s.charAt(i) == ' ') {
                if (builder.length() > 0) {
                    builder.append(' ');
                }
              // Lấy từ kí tự cuối từ phải qua trái
                builder.append(s.substring(i + 1, currentWordEnd));
                currentWordEnd = i;
            }
        }
        String firstWord = s.substring(0, currentWordEnd);
        if (builder.length() > 0) {
            builder.append(" ");
        }
        builder.append(firstWord);
        return builder.toString();
    }
}

Ngoài Reverse Array, cũng có những bài mở rộng hơn là tìm kiếm 2 vị trí trong array sao cho tổng là một số nguyên (target nhất định). Ước định rằng array đã được sort từ ban đầu. Ta cũng có thể lặp từ start tới end, tăng start nếu sum nhỏ hơn target và giảm end nếu sum đã lớn hơn target

package com.src;

public class Main {
    public static void main(String[] args) {
        int[] a = new int[]{1, 2, 3, 5, 6, 7};
        System.out.println(twoSum(a, 11));
    }

    public static int twoSum(int[] a, int target) {
       int start = 0;
       int end = a.length - 1;

       while (start < end) {
           int sum = a[start] + a[end];
           if (sum < target) {
               start++;
           }
           if (sum > target) {
               end--;
           }
           if (sum == target)
               return a[start] + a[end];
       }
       return 0;
    }
}

4. Tham khảo

Thank you so much for your time – Have a nice day – Happy coding!

Có gì thắc mắc cứ comment đây nha! - Please feel free to comment here!

Kiên Nguyễn

👋 HEY THERE! 👋. My pleasure when you're here to read the article. Please feel free to comment, send a message or just want to say HELLO. Thank you, from bottom of my heart ❤️❤️❤️. Visit my portfolio: https://kieblog.com

Mời tui ly cà phê

Like page để không bỏ lỡ bài viết mới
Facebook Pagelike Widget
Bài viết mới
Lưu trữ