按排序顺序打印字符串数组,而不将一个字符串复制到另一个字符串中

2021年3月12日14:11:47 发表评论 841 次浏览

本文概述

给定一个由n个字符串组成的数组。任务是按排序顺序打印字符串。该方法应确保在排序过程中不应将任何字符串复制到另一个字符串。

例子:

Input : {"geeks", "for", "geeks", "quiz")
Output : for geeks geeks quiz

Input : {"ball", "pen", "apple", "kite"}
Output : apple ball kite pen

推荐:请尝试使用{IDE}首先, 在继续解决方案之前。

方法:它具有以下步骤:

  1. 维护另一个阵列indexed_arr存储/维护每个字符串的索引。
  2. 我们可以对此应用任何排序技术indexed_arr.

插图:

--> str[] = {"world", "hello"}
--> corresponding index array will be
    indexed_arr = {0, 1}
--> Now, how the strings are compared and 
    accordingly values in indexed_arr are changed.
--> Comparison process:
    if (str[index[0]].compare(str[index[1]] > 0
        temp = index[0]
        index[0] = index[1]
        index[1] = temp

// after sorting values of
// indexed_arr = {1, 0}
--> for i=0 to 1
        print str[index[i]]

This is how the strings are compared and their 
corresponding indexes in the indexed_arr
are being manipulated/swapped so that after the sorting process
is completed, the order of indexes in the indexed_arr
gives us the sorted order of the strings.

C ++

// C++ implementation to print array of strings in sorted
// order without copying one string into another
#include <bits/stdc++.h>
  
using namespace std;
  
// function to print strings in sorted order
void printInSortedOrder(string arr[], int n)
{
     int index[n];
     int i, j, min;
      
     // Initially the index of the strings
     // are assigned to the 'index[]' 
     for (i=0; i<n; i++)
         index[i] = i;
      
     // selection sort technique is applied    
     for (i=0; i<n-1; i++)    
     {
         min = i;
         for (j=i+1; j<n; j++)
         {
             // with the help of 'index[]'
             // strings are being compared
             if (arr[index[min]].compare(arr[index[j]]) > 0)
                 min = j;
         }
          
         // index of the smallest string is placed
         // at the ith index of 'index[]'
         if (min != i)
         {
             int temp = index[min];
             index[min] = index[i];
             index[i] = temp;
         }
     }
      
     // printing strings in sorted order
     for (i=0; i<n; i++)
         cout << arr[index[i]] << " " ;
}
  
// Driver program to test above
int main()
{
     string arr[] = { "geeks" , "quiz" , "geeks" , "for" };
     int n = 4;
     printInSortedOrder(arr, n);
     return 0;
}

Java

//Java implementation to print array of strings in sorted
// order without copying one string into another
  
class GFG {
  
     // function to print strings in sorted order
     static void printInSortedOrder(String arr[], int n) {
         int index[] = new int [n];
         int i, j, min;
  
         // Initially the index of the strings
         // are assigned to the 'index[]' 
         for (i = 0 ; i < n; i++) {
             index[i] = i;
         }
  
         // selection sort technique is applied    
         for (i = 0 ; i < n - 1 ; i++) {
             min = i;
             for (j = i + 1 ; j < n; j++) {
                 // with the help of 'index[]'
                 // strings are being compared
                 if (arr[index[min]].compareTo(arr[index[j]]) > 0 ) {
                     min = j;
                 }
             }
  
             // index of the smallest string is placed
             // at the ith index of 'index[]'
             if (min != i) {
                 int temp = index[min];
                 index[min] = index[i];
                 index[i] = temp;
             }
         }
  
         // printing strings in sorted order
         for (i = 0 ; i < n; i++) {
             System.out.print(arr[index[i]] + " " );
         }
     }
  
     // Driver program to test above
     static public void main(String[] args) {
         String arr[] = { "geeks" , "quiz" , "geeks" , "for" };
         int n = 4 ;
         printInSortedOrder(arr, n);
     }
}
  
// This code is contributed by 29AjayKumar

Python 3

# Python 3 implementation to print array 
# of strings in sorted order without 
# copying one string into another
  
# function to print strings in sorted order
def printInSortedOrder(arr, n):
     index = [ 0 ] * n
      
     # Initially the index of the strings
     # are assigned to the 'index[]' 
     for i in range (n):
         index[i] = i
      
     # selection sort technique is applied 
     for i in range (n - 1 ):
         min = i
         for j in range (i + 1 , n):
              
             # with the help of 'index[]'
             # strings are being compared
             if (arr[index[ min ]] > arr[index[j]]):
                 min = j
          
         # index of the smallest string is placed
         # at the ith index of 'index[]'
         if ( min ! = i):
             index[ min ], index[i] = index[i], index[ min ]
      
     # printing strings in sorted order
     for i in range (n):
         print (arr[index[i]], end = " " )
  
# Driver Code
if __name__ = = "__main__" :
      
     arr = [ "geeks" , "quiz" , "geeks" , "for" ]
     n = 4
     printInSortedOrder(arr, n)
  
# This code is contributed by ita_c

C#

//C# implementation to print an array of strings in sorted
// order without copying one string into another
  using System;
public class GFG {
   
     // function to print strings in sorted order
     static void printInSortedOrder(String []arr, int n) {
         int []index = new int [n];
         int i, j, min;
   
         // Initially the index of the strings
         // are assigned to the 'index[]' 
         for (i = 0; i < n; i++) {
             index[i] = i;
         }
   
         // selection sort technique is applied    
         for (i = 0; i < n - 1; i++) {
             min = i;
             for (j = i + 1; j < n; j++) {
                 // with the help of 'index[]'
                 // strings are being compared
                 if (arr[index[min]].CompareTo(arr[index[j]]) > 0) {
                     min = j;
                 }
             }
   
             // index of the smallest string is placed
             // at the ith index of 'index[]'
             if (min != i) {
                 int temp = index[min];
                 index[min] = index[i];
                 index[i] = temp;
             }
         }
   
         // printing strings in sorted order
         for (i = 0; i < n; i++) {
             Console.Write(arr[index[i]] + " " );
         }
     }
   
     // Driver program to test above
     static public void Main() {
         String []arr = { "geeks" , "quiz" , "geeks" , "for" };
         int n = 4;
         printInSortedOrder(arr, n);
     }
}
   
// This code is contributed by 29AjayKumar

输出如下:

for geeks geeks quiz

时间复杂度:上2)

当我们必须最小化数量时, 可以使用该方法光盘刻录就像一系列结构一样。比较结构值, 但不交换它们的值, 而是将它们的索引保存在另一个数组中, 对该数组进行操作以使索引保持顺序, 该顺序代表结构的排序数组。

行使:在合并排序, 插入排序等其他排序技术的帮助下应用此方法。

如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

木子山

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: