Kth ລັກສະນະບໍ່ເຮັດຊ້ ຳ


ລະດັບຄວາມຫຍຸ້ງຍາກ Easy
ຖາມເລື້ອຍໆໃນ Amazon ຈາກຫນາກແອບເປີ Bloomberg ເຟສບຸກ Goldman Sachs ກູໂກ Microsoft Oracle Zillow
Hash ແຮກ HashMap string

ຖະແຫຼງການບັນຫາ

ໃນ“ ຕົວອັກສອນທີ່ບໍ່ເຮັດຊ້ ຳ” Kth ພວກເຮົາໄດ້ໃຫ້ string “ s”. ຂຽນໂປຼແກຼມເພື່ອຊອກຫາ kcha ທີ່ບໍ່ເຮັດຊ້ ຳ ອີກຄັ້ງ. ຖ້າມີຕົວອັກສອນນ້ອຍກ່ວາ k ທີ່ບໍ່ຊ້ ຳ ຊ້ ຳ ໃນສາຍແລ້ວພິມ“ -1”.

ຮູບແບບການປ້ອນຂໍ້ມູນ

ແຖວ ທຳ ອິດແລະພຽງເສັ້ນດຽວທີ່ມີສາຍ“ s”.

ຮູບແບບຜົນໄດ້ຮັບ

ສາຍ ທຳ ອິດແລະພຽງເສັ້ນດຽວທີ່ບັນຈຸ a_character ທີ່ເປັນຕົວແທນຂອງ kth ທີ່ບໍ່ເຮັດຊ້ ຳ ອີກຄັ້ງ. ຖ້າມີຕົວອັກສອນນ້ອຍກ່ວາ k ທີ່ບໍ່ຊ້ ຳ ຊ້ ຳ ໃນສາຍແລ້ວພິມ“ -1”.

ຍົກຕົວຢ່າງ

tutorialcup
3
i

ຄໍາອະທິບາຍ: ທີ່ນີ້ freq [t] ແມ່ນ 2, freq [u] ແມ່ນ 2, ແລະສ່ວນທີ່ເຫຼືອຂອງ char ອື່ນໆທີ່ມີ freq 1. ດັ່ງນັ້ນ Kth ທີ່ບໍ່ເຮັດຊ້ ຳ ອີກຄັ້ງ - "ຫຼື".

ລະບົບວິເຄາະ

1. ສ້າງແຖວນັບເພື່ອເກັບ ຈຳ ນວນຕົວອັກສອນໃນແຖວ.

2. ສ້າງຕາຕະລາງດັດສະນີເພື່ອເກັບຮັກສາດັດສະນີຂອງໂຕອັກສອນທີ່ບໍ່ຊ້ ຳ.

3. ຖ້າຕົວອັກສອນ 'x' ກຳ ລັງເຮັດຊ້ ຳ ອີກຫຼືບໍ່ມີຢູ່ໃນຮ້ານ string n ໃນຕາຕະລາງດັດສະນີ.

4. ເລີ່ມຕົ້ນແຖວນັບດ້ວຍເລກສູນແລະດັດຊະນີດັດສະນີກັບ n. (n ແມ່ນຄວາມຍາວຂອງຊ່ອຍແນ່)

5. ຂ້າມສາຍປ້ອນຂໍ້ມູນ x = str [i]

6. ຈຳ ນວນເພີ່ມ [x]

7. ຖ້ານັບ [x] = 1, ຫຼັງຈາກນັ້ນເກັບຄ່າດັດຊະນີ x ໃນດັດຊະນີ [x]. index [x] = i

8. ຖ້ານັບ [x] = 2, ຫຼັງຈາກນັ້ນເອົາ x ຈາກດັດຊະນີ []. ດັດສະນີ [x] = ນ.

9. ຮຽງແຖວຂອງດັດຊະນີ.

10​. ດັດສະນີ [k] ແມ່ນຕົວອັກສອນທີ່ບໍ່ຊ້ ຳ ອີກ.

ການປະຕິບັດ

C ++ Program ເພື່ອຊອກຫາຕົວອັກສອນທີ່ບໍ່ເຮັດຊ້ ຳ ຄືນ Kth

#include <bits/stdc++.h>
using namespace std;

int main()
{
   string s;
   cin>>s;
   int k;
   cin>>k;
   int n=s.length();
   int count[256];
   int index[256];
   memset(count,0,sizeof(count));
   for(int i=0;i<256;i++)
   {
       index[i]=n;
   }
   for(int i=0;i<n;i++)
   {
        count[s[i]]++;
        if(count[s[i]]==1)
        {
            index[s[i]]=i;
        }
        if(count[s[i]]==2)
        {
            index[s[i]]=n;
        }
   }
   sort(index, index+256);
    if(index[k-1]!=n)
    {
        cout<<s[index[k-1]]<<endl;  
    }
    else
    {
        cout<<-1<<endl;
    }
   return 0;
}

Java Program ເພື່ອຊອກຫາຕົວອັກສອນທີ່ບໍ່ເຮັດຊ້ ຳ ຄືນ Kth

import java.util.Arrays;
import java.util.Scanner;

class sum
{ 
  public static void main(String[] args) 
  { 
    Scanner sr = new Scanner(System.in); 
                String s = sr.next();
                int k=sr.nextInt();
                int n=s.length();
                int freq[] = new int [256];
                int index[] = new int [256];
                for(int i=0;i<256;i++)
                {
                    freq[i]=0;
                    index[i]=n;
                }
                for(int i=0;i<n;i++) 
                {
                    freq[s.charAt(i)]++; 
                    if(freq[s.charAt(i)]==1) 
                    { 
                        index[s.charAt(i)]=i; 
                    } 
                    if(freq[s.charAt(i)]==2) 
                    {
                        index[s.charAt(i)]=n;
                    }
                }
                Arrays.sort(index);
                if(index[k-1]!=n) 
                {
                    System.out.println(s.toCharArray()[index[k-1]]); 
                }
                else
                {
                    System.out.println(-1); 
                }
  } 
} 
tutorialcup
3
i

ການວິເຄາະທີ່ສັບສົນເພື່ອຊອກຫາຕົວອັກສອນທີ່ບໍ່ຊ້ ຳ ຊາກ Kth

ຄວາມສັບສົນເວລາ

O (n) ບ່ອນທີ່ n ແມ່ນຂະ ໜາດ ຂອງອາເລທີ່ໃຫ້. ໃນທີ່ນີ້ພວກເຮົາພຽງແຕ່ຜ່ານສາຍ“ s” ແລະນັບຄວາມຖີ່ຂອງແຕ່ລະຕົວລະຄອນ. ຫລັງຈາກນັ້ນປະຕິບັດການ ດຳ ເນີນງານບາງຢ່າງຕາມຄວາມຕ້ອງການໃນເວລາຄົງທີ່

ຄວາມສັບສົນໃນອະວະກາດ

O (1) ເນື່ອງຈາກວ່າໃນທີ່ນີ້ພວກເຮົາພຽງແຕ່ໃຊ້ພື້ນທີ່ຄົງທີ່ຂອງ 256 ຂະ ໜາດ. ໃນທີ່ນີ້ພວກເຮົາເກັບຮັກສາຄວາມຖີ່ແລະດັດສະນີຂອງແຕ່ລະຕົວລະຄອນ.