資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會科學
時尚研究
法律研究如何使用 C# 查詢給定字串中到某個字元的最短距離？
建立 2 個不同的陣列 leftDis 和 rightDis。leftDis 將儲存從左側移動時的值。rightDis 將儲存從右側移動時的最短值。每當遇到字元時，新增字元所在的位置到陣列。最後一步計算兩個陣列的最小值。
時間複雜度 − O(n)
空間複雜度 − O(n)
示例
public class Arrays{
public int[] ShortestDistanceToCharacter(string s, char c){
int stringLength = s.Length;
int[] leftDis = new int[s.Length];
int[] rightDis = new int[s.Length];
leftDis = Enumerable.Range(0, s.Length).Select(n => int.MinValue).ToArray();
rightDis = Enumerable.Range(0, s.Length).Select(n => int.MaxValue).ToArray();
int count = int.MaxValue;
for (int i = 0; i < rightDis.Length; i++){
if (s[i] == c){
count = 0;
rightDis[i] = count;
}
else{
if (count != int.MaxValue){
count++;
rightDis[i] = count;
}
}
}
count = int.MaxValue;
for (int i = leftDis.Length - 1; i >= 0; i--){
if (s[i] == c){
count = 0;
leftDis[i] = count;
}
else{
if (count != int.MaxValue){
count++;
leftDis[i] = count;
}
}
}
int[] ans = new int[stringLength];
for (int i = 0; i < stringLength - 1; i++){
ans[i] = Math.Min(leftDis[i], rightDis[i]);
}
return ans;
}
}
static void Main(string[] args){
Arrays s = new Arrays();
string ss = "lovecode";
char c = 'e';
var res = s.ShortestDistanceToCharacter(ss, c);
foreach (var item in res){
Console.WriteLine(item);
}
}輸出
[3,2,1,0,1,2,1,0]
更新時間： 2021 年 8 月 17 日
322 次瀏覽
廣告