首页 > 试题广场 >

在有序但是含有空的数组中查找字符串

[编程题]在有序但是含有空的数组中查找字符串
  • 热度指数：1708 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个字符串数组strs[]，在strs中有些位置为null，但在不为null的位置上，其字符串是按照字典序由小到大出现的。在给定一个字符串str，请返回str在strs中出现的最左位置，如果strs中不存在str请输出“-1”。

输入描述:
输出包含多行，第一行包含一个整数n代表strs的长度，第二行一个字符串，代表str，接下来n行，每行包含一个字符串构成，字符串只包含小写字符，如果这一行为“0”，代表该行字符串为空，这n行字符串代表strs。（数据保证当字符串不为空时，所有字符均为小写字母；保证所有的字符串长度都小于10，）


输出描述:
输出一个整数，代表要返回的值。
示例1

输入

8 
a
0
a
0
a
ab
ac
0
b

输出

1

说明

在strs中，最左边的“a”在位置1，strs为[null,"a",null,"a","ab","ac",null,"b"]
示例2

输入

4
grep
awk
grep
0
sed

输出

1

说明

strs为["awk","grep",null,"sed"],grep在位置1

备注:
时间复杂度,额外空间复杂度。
算法知识视频讲解
添加回答
无心2019头像 无心2019 
#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin>>n;
    string str,s;
    cin>>str;
    for(int i=0;i<n;i++){
        cin>>s;
        if(s==str)
        {
            cout<<i<<endl;
            return 0;
        }
    }
    cout<<-1<<endl;
    return 0;
}

发表于 2019-09-13 21:09:44 回复(2)
C
helloxuanbao头像 helloxuanbao 
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAXLEN 11
#define MAXN 100000

bool isNull(char *str) {
    return strlen(str) == 1 && str[0] == '0';
}

int main(void) {
    int n, l, r, m, res = -1, cmp;
    char strs[MAXN][MAXLEN], str[MAXLEN];
    scanf("%d%s", &n, str);
    for (int i = 0; i < n; i++) {
        scanf("%s", strs[i]);
    }
    
    l = 0, r = n - 1;
    while (l <= r) {
        m = l + ((r - l) >> 1);
        if (isNull(strs[m])) {
            int i = m - 1;
            while (i >= l && isNull(strs[i])) i--;
            if (i < l || strcmp(strs[i], str) < 0) {
                l = m + 1;
            } else {
                r = i - 1;
                if (strcmp(strs[i], str) == 0) res = i;
            }
        } else {
            if (strcmp(strs[m], str) < 0) {
                l = m + 1;
            } else {
                r = m - 1;
                if (strcmp(strs[m], str) == 0) res = m;
            }
        }
    }
    printf("%d\n", res);
    return 0;
}

发表于 2022-02-06 16:52:32 回复(0)
Java
pein531头像 pein531
把每个字符串第一次出现的位置保存在哈希表里，然后进行查询就行 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.LinkedList;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String query = br.readLine();
        HashMap<String, Integer> map = new HashMap<>();
        for(int i = 0; i < n; i++){
            String str = br.readLine();
            if(!map.containsKey(str)) map.put(str, i);
        }
        System.out.println(map.getOrDefault(query, -1));
    }
}

发表于 2021-11-17 14:23:58 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    string s, t;
    int n, k=-1;
    cin>>n>>s;
    for(int i=0;i<n;i++){
        cin>>t;
        if(k==-1 && t==s)
            k = i;
    }
    cout<<k<<endl;
    return 0;
}

发表于 2020-04-16 23:47:58 回复(0)
Java
deh头像 deh
输入的时候把0改成null，我个憨憨改成 “”然后debug了半天。。。 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

    public static int getIndex(String[] strs, String str) {
        if (strs == null || str == null || strs.length == 0) {
            return -1;
        }
        int res = -1;
        int left = 0;
        int right = strs.length - 1;
        int mid = 0;
        int i = 0;
        while (left <= right) {
            mid = (left + right) / 2;
            // mid非空并且命中，还要继续往左找找看
            if (strs[mid] != null && strs[mid].equals(str)) {
                res = mid;
                right = mid - 1;
            } else if (strs[mid] != null) {
                // mid非空，比较字典序
                if (strs[mid].compareTo(str) < 0) {
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                // str[mid]为空
                i = mid;
                // 从mid开始从右到左遍历左半区
                while (strs[i] == null && --i >= left) {
                }
                if (i < left || strs[i].compareTo(str) < 0) {
                    left = mid + 1;
                } else {
                    res = strs[i].equals(str) ? i : res;
                    right = i - 1;
                }
            }
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        String str = bf.readLine();
        String[] data = new String[n];
        for (int i = 0; i < n; i++) {
            data[i] = bf.readLine();
            data[i] = data[i].equals("0") ? null : data[i];
        }
        bf.close();
        System.out.println(getIndex(data, str));
    }
    
}

发表于 2020-04-06 23:34:35 回复(1)
我心踏雪了无痕头像 我心踏雪了无痕
二分查找（递归） 
import java.util.*;
import java.io.*;
public class Main{
    public static void main (String[] args) throws IOException{
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(b.readLine());
        String str = b.readLine();
        String[] arr = new String[n];
        for(int i = 0; i<n ;i++){
            arr[i] = b.readLine();
            arr[i] = arr[i].equals("0") ? null : arr[i];
        }
        b.close();
        
        System.out.println(get(arr, str, 0, arr.length -1));
    }
    public static int get(String[] arr, String s, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid = start + ((end - start)>>1);
        if (arr[mid]==null) {
            int left = mid, right = mid;
            while ((arr[left]==null && arr[right]==null) ||
                    (left == start && right == end)) {
                if (left > start) {
                    left--;
                }
                if (right < end) {
                    right++;
                }
            }
            if (arr[left]!=null) {
                return core(arr, s, start, end, left);
            } else if (arr[right]!=null) {
                return core(arr, s, start, end, right);
            }
            return -1;
        }
        return core(arr, s, start, end, mid);
    }
    public static int core(String[] arr, String s, int start, int end, int cur) {
        if (arr[cur].compareTo(s) < 0) {
            return get(arr, s, cur + 1, end);
        } else if(arr[cur].compareTo(s) > 0) {
            return get(arr, s, start, cur - 1);
        }
        return cur;
    }
}
二分查找（迭代） 
import java.util.*;
import java.io.*;
public class Main{
    public static void main (String[] args) throws IOException{
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(b.readLine());
        String str = b.readLine();
        String[] arr = new String[n];
        for(int i = 0; i<n ;i++){
            arr[i] = b.readLine();
            arr[i] = arr[i].equals("0") ? null : arr[i];
        }
        b.close();
        
        System.out.println(get(arr, str, 0, arr.length -1));
    }
    public static int get(String[] arr, String s, int start, int end) {
        if (arr == null || arr.length < 1 || s == null){
            return -1;
        }
        int mid = 0;
        while(start <= end ) {
            mid = start + ((end - start)>>1);
            while (start<=end && arr[mid]==null) {
                while (mid > start && arr[mid]==null) {
                    mid--;
                }
                if (arr[mid]==null) {
                    start = start + ((end - start)>>1) + 1;
                    mid = start + ((end - start)>>1);
                }
            }
            if (start > end) {
                break;
            }
            if (arr[mid].compareTo(s) == 0) {
                return mid;
            } else if (arr[mid].compareTo(s) > 0) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
            
        }
        return -1;
    }
}



编辑于 2019-10-25 04:55:34 回复(0)
Cheng～千禧头像 Cheng～千禧 
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;


int getIndex(vector<string> &strs, string str) {
    if (strs.empty() || strs.size() == 0 || str.empty()) {
        return -1;
    }
    int res = -1;
    int left = 0;
    int right = strs.size() - 1;
    int mid = 0;
    int i = 0;
    while (left <= right) {
        mid = (left + right) / 2;
        if (!strs[mid].empty() && strs[mid].compare(str) == 0) {
            res = mid;
            right = mid - 1;
        } else if (!strs[mid].empty()) {
            if (strs[mid].compare(str) < 0) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        } else {
            i = mid;
            while (strs[i].empty() && --i >= left) {
                ;    // 即重复执行while中的语句直至不符合条件为止
            }
            if (i < left || strs[i].compare(str) < 0) {
                left = mid + 1;
            } else {
                res = strs[i].compare(str) == 0 ? i : res;
                right = i - 1;
            }
        }
    }
    return res;
}

int main () {
    int len;
    string str;
    cin>>len>>str;
    vector<string> strs(len);
    for (int i = 0; i < len; i++) {
        cin>>strs[i];
        strs[i] = strs[i].compare("0") == 0 ? "" : strs[i];
    }
    int res = getIndex(strs, str);
    cout<<res<<endl;
    return 0;
}

发表于 2020-09-01 19:57:09 回复(0)
C/C++
别搁那忽悠人了头像 别搁那忽悠人了 
#include<iostream>
(720)#include <string>
#include <vector>
using namespace std;
int getleft(vector<string> strs, string str)
{
	if (strs.size() == 0 || str.size() == 0)
		return -1;
	int res = -1;
	int left = 0;
	int right = strs.size() - 1;
	int mid = 0;
	int i = 0;
	while (left <= right)
	{
		mid = (left + right) / 2;
		if (strs[mid] == str)
		{
			res = mid;
			right = mid - 1;
		}
		else if (strs[mid] != "0")
		{
			if (strs[mid] > str)
				right = mid - 1;
			else
				left = mid + 1;
		}
		else {
			i = mid;
			while (strs[i] == "0" && --i >= left);
			if (i < left || strs[i] < str)
				left = mid + 1;
			else
			{
				res = strs[i] == str ? i : res;
				right = i - 1;
			}
		}
	}
	return res;
}
int main()
{
	int n;
	cin >> n;

	vector<string> strv;
	string s;
	for (int i = 0; i < n; i++){
		cin >> s;

		strv.push_back(s);
	}
	string a;
	cin >> a;


	cout << getleft(strv, a) << endl;

	//system("pause");
	return 0;

}
有大神帮忙看一下么
百分之20
漏洞百出
心态有点崩
发表于 2020-05-08 13:41:10 回复(0)
復活の検事头像 復活の検事 
import java.util.Scanner;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()){
            int num = scanner.nextInt();
            String str = scanner.next();
            String[] strs = new String[num];
            for(int i=0;i<num;i++){
                String input = scanner.next();
                if(input.equals("0")){
                    strs[i] = null;
                }else{
                    strs[i] = input;
                }
            }
            System.out.println(getIndex(strs, str));
        }
    }

    public static int getIndex(String[] strs, String str){
        if(strs == null || strs.length == 0 || str == null){
            return -1;
        }
        // result表示str在strs中最左的位置
        int result = -1;
        int left = 0;
        int right = strs.length-1;
        int mid = 0;
        // i存放不为null的位置
        int i;

        while(left <= right){
            mid = (left+right)/2;
            if(strs[mid] != null && strs[mid].equals(str)){  // 中间值不为空且恰好匹配
                result = mid;
                right = mid-1;
            }else if(strs[mid] != null){  // 中间值不为空且不匹配
                if(strs[mid].compareTo(str) < 0){  // 字典序比待求串小，所以往右找
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
            }else{  // 中间值为空，则须先往左查找不空的地方
                i = mid;
                while(strs[i] == null && --i >= left){

                }
                if(i<left || strs[i].compareTo(str)<0){
                    left = mid+1;
                }else{
                    result = strs[i].equals(str) ? i : result;
                    right = i-1;
                }
            }
        }
        return result;
    }


}

发表于 2020-05-06 13:45:09 回复(0)
包子冲汤胡辣汤头像 包子冲汤胡辣汤 
#include<cstdio>
(802)#include<string>
#include<vector>
(721)#include<iostream>
using namespace std;
struct node{
    string s;
    int pos;
};
vector<node> v;
int main(){
    int n;
    string s,s1;
    string s2="0";
    while(scanf("%d",&n)!=EOF){
    cin>>s;
    v.resize(n);
    int k=0;
    for(int i=0;i<n;++i){
        cin>>s1;
        if(s1!=s2){
           v[k].pos=i;
           v[k].s=s1;
           ++k;
        }
    }
    int left=0,right=k-1,in;
    while(left<=right){
        in=(left+right)/2;
        if(v[in].s>=s){
            right=in-1;
        }else{
            left=in+1;
        }
    }
    if(v[left].s!=s)
      printf("-1\n");
    else
      printf("%d\n",v[left].pos);
    }
    return 0;
}

发表于 2020-03-25 18:40:25 回复(0)
双剑华斩丨永恩头像 双剑华斩丨永恩
没有写二分
C语言版本 
#include <stdio.h>
#include <string.h>

int main(){
    int n ;
    char strs[100000][10];
    char str[10];
    scanf("%d", &n);
    getchar();
    gets(str);
    int i = 0;
    for(i = 0; i < n; i++)
    {
        gets(strs[i]);
        if("" != strs[i] && strcmp(strs[i], str)==0){
            printf("%d\n", i);
            return 0;
        }
    }

    printf("-1\n");
    
    return 0;
}


发表于 2019-11-29 11:20:39 回复(0)
我要收offer头像 我要收offer 
题目要求：
时间复杂度O（log _{2}n）O（log2n）,额外空间复杂度O（1）O（1）。
本题使用的是二分查找法。 
import java.io.*;
public class Main{
    public static void main (String []args)throws IOException{
        BufferedReader b = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(b.readLine());
        String str = b.readLine();
        String[] arr = new String[n];
        for(int i = 0; i<n ;i++){
            arr[i] = b.readLine();
            arr[i] = arr[i].equals("0") ? null : arr[i];
        }
        b.close();
        
        System.out.println(binarySearch(arr, str, 0, arr.length -1));
    }
    public static int binarySearch(String [] arr, String str , int s, int e){
        if(s > e)
            return -1;
        int m = (s+e)/2;
        
        if(arr[m] != null){//中位串不是null
            if(str.equals(arr[m])){//中位串与目标串str相同，则求左边子数组中有没有str。
                //若有则返回左边子数组中的第一个str的位置,否则返回midlle。
                int temp = binarySearch(arr, str, s, m-1);
                return temp == -1 ? m : temp;
            }else if(str.compareTo(arr[m]) > 0){//中位串大于目标串str
                return binarySearch(arr, str, m+1, e);
            }else{//中位串小于目标串str
                return binarySearch(arr, str, s, m-1);
            }
        }else{//中位串是null
            int temp = binarySearch(arr, str,s,m-1);//求左边子数组中str的最左位置
            //若有则返回左边子数组中的第一个str的位置,否则返回右边子数组str的最左位置。
            return temp == -1 ? binarySearch(arr, str, m+1, e) : temp;
        }
    }
}   


发表于 2019-09-29 00:40:43 回复(0)
提交观点

问题信息

字符串 哈希
上传者：小小
难度：
12条回答 3395浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号