הסרת דמויות חוזרות ממחרוזת
1. סקירה כללית
במדריך זה נדון בכמה טכניקות ב- Java כיצד להסיר תווים חוזרים ממחרוזת.
לכל טכניקה, נדבר בקצרה על זמנו ומורכבותו בחלל.
2. שימוש מוּבהָק
נתחיל בהסרת הכפילויות מהמחרוזת שלנו באמצעות ה- מוּבהָק שיטה שהוצגה ב- Java 8.
להלן, אנו מקבלים מופע של Intסלקצץ מאובייקט מחרוזת נתון. ואז, אנו משתמשים ב- מוּבהָק שיטה להסרת הכפילויות. לבסוף, אנו קוראים ל- לכל אחד שיטה לולאה על הדמויות המובחנות ולצרף אותן לדפים שלנו StringBuilder:
StringBuilder sb = StringBuilder חדש (); str.chars (). מובחן (). forEach (c -> sb.append ((char) c));מורכבות זמן: עַל) - זמן הריצה של הלולאה הוא ביחס ישר לגודל מחרוזת הקלט
מרחב עזר:עַל) - מאז מוּבהָק משתמש ב- LinkedHashSet באופן פנימי ואנו שומרים את המחרוזת שהתקבלה ב- StringBuilder לְהִתְנַגֵד
שומר על הסדר: כן - מאז LinkedHashSet שומר על סדר היסודות שלו
ולמרות שזה נחמד שג'אווה 8 עושה את המשימה הזו בשבילנו כל כך יפה, בואו נשווה אותה למאמצים לגלגל את עצמנו.
3. שימוש אינדקס של
הגישה הנאיבית להסרת כפילויות ממחרוזת פשוט כוללת לולאה על הקלט ושימוש ב- אינדקס של שיטה לבדוק אם התו הנוכחי כבר קיים במחרוזת שהתקבלה:
StringBuilder sb = StringBuilder חדש (); int idx; עבור (int i = 0; i <str.length (); i ++) {char c = str.charAt (i); idx = str.indexOf (c, i + 1); אם (idx == -1) {sb.append (c); }} מורכבות זמן: O (n * n) עבור כל דמות, אינדקס של השיטה עוברת דרך המחרוזת שנותרה
מרחב עזר:עַל) - שטח ליניארי נדרש מכיוון שאנו משתמשים ב- StringBuilder לאחסון התוצאה
שומר על הסדר: כן
לשיטה זו מורכבות שטח זהה לגישה הראשונה אך מבצע הרבה יותר לאט.
4. שימוש במערך תווים
אנחנו יכולים גם להסיר כפילויות מהמחרוזת שלנו על ידי להמיר אותו לא לְהַשְׁחִיר מערך ואז עוקב אחר כל תו והשווה אותו לכל התווים הבאים.
כפי שניתן לראות להלן, אנו יוצרים שניים ל לולאות ואנחנו בודקים אם כל אלמנט חוזר על עצמו במחרוזת. אם נמצא כפילויות, איננו מצרפים אותו ל- StringBuilder:
char [] chars = str.toCharArray (); StringBuilder sb = StringBuilder חדש (); בוליאני חזר על עצמו צ'אר; עבור (int i = 0; i <chars.length; i ++) {repeatChar = false; עבור (int j = i + 1; j <chars.length; j ++) {if (chars [i] == chars [j]) {repeatChar = true; לשבור; }} אם (! repeatChar) {sb.append (chars [i]); }} מורכבות זמן: O (n * n) - יש לנו לולאה פנימית וחיצונית שניהם חוצים את מחרוזת הקלט
מרחב עזר:עַל) נדרש מרחב ליניארי מאז צ'ארס משתנה מאחסן עותק חדש של קלט המחרוזת ואנחנו משתמשים גם ב- StringBuilder כדי לשמור את התוצאה
שומר על הסדר: כן
שוב, הניסיון השני שלנו מתפקד בצורה גרועה בהשוואה להיצע Core Java, אבל בואו נראה לאן נגיע עם הניסיון הבא שלנו.
5. שימוש במיון
לחלופין, ניתן לבטל תווים חוזרים על ידי מיון מחרוזת הקלט שלנו לכפילויות קבוצתיות. על מנת לעשות זאת, עלינו להמיר את המחרוזת ל- a צ'אר אלצייר ולמיין אותו באמצעות מערכים.סוג שיטה. לבסוף, אנו נעבור על מיון לְהַשְׁחִיר מַעֲרָך.
במהלך כל איטרציה, אנו נשווה כל אלמנט במערך לאלמנט הקודם. אם האלמנטים שונים אז נספח את התו הנוכחי ל StringBuilder:
StringBuilder sb = StringBuilder חדש (); אם (! str.isEmpty ()) {char [] chars = str.toCharArray (); Arrays.sort (תווים); sb.append (תווים [0]); עבור (int i = 1; i <chars.length; i ++) {if (chars [i]! = chars [i - 1]) {sb.append (chars [i]); }}}מורכבות זמן: O (n יומן n) - המיון משתמש ב- Quicksort בעל ציר כפול המציע ביצועי O (n log n) במערכי נתונים רבים
מרחב עזר:עַל) - מאז toCharArray השיטה יוצרת עותק של הקלט חוּט
שומר על הסדר: לא
בואו ננסה את זה שוב עם הניסיון האחרון שלנו.
6. שימוש ב- מַעֲרֶכֶת
דרך נוספת להסיר תווים חוזרים ונשנים ממחרוזת היא באמצעות a מַעֲרֶכֶת. אם לא אכפת לנו מסדר התווים במחרוזת הפלט שלנו נוכל להשתמש ב- HashSet.אחרת, אנו יכולים להשתמש ב- LinkedHashSet כדי לשמור על צו הכניסה.
בשני המקרים נעבור על מחרוזת הקלט ונוסיף כל תו ל מַעֲרֶכֶת. לאחר שהדמויות יוכנסו לסט, נעבור עליה כדי להוסיף אותן ל StringBuilder והחזיר את המחרוזת שהתקבלה:
StringBuilder sb = StringBuilder חדש (); הגדר linkedHashSet = חדש LinkedHashSet (); עבור (int i = 0; i <str.length (); i ++) {linkedHashSet.add (str.charAt (i)); } עבור (תו c: linkedHashSet) {sb.append (c); } מורכבות זמן: עַל) - זמן הריצה של הלולאה הוא ביחס ישר לגודל מחרוזת הקלט
מרחב עזר:עַל) - שטח נדרש עבור מַעֲרֶכֶת תלוי בגודל מחרוזת הקלט; כמו כן, אנו משתמשים ב- StringBuilder לאחסון התוצאה
שומר על הסדר:LinkedHashSet - כן, HashSet - לא
ועכשיו התאמנו את גישת Core Java! זה לא מאוד מזעזע לגלות שזה דומה מאוד למה מוּבהָק כבר עושה.
7. מסקנה
במאמר זה סקרנו כמה דרכים להסרת תווים חוזרים ממחרוזת ב- Java. בדקנו גם את מורכבות הזמן והמרחב של כל אחת משיטות אלה.
כמו תמיד, ניתן למצוא קטעי קוד ב- GitHub.
