我的Java代碼如下。boolean almostIncreasingSequence(int[] sequence) { Integer[] arr = new Integer[sequence.length]; for(int ctr = 0; ctr < sequence.length; ctr++) { arr[ctr] = Integer.valueOf(sequence[ctr]); // returns Integer value } System.out.println("Integer :: " + arr); List<Integer> al = new ArrayList<Integer>(); // adding elements of array to arrayList. Collections.addAll(al, arr); System.out.println("list :: " + al); int save, flag = 0; for(int i=0; i<al.size(); i++) { save = al.get(i); al.remove(i); if(al.size()==1) return true; for(int j=0; j<al.size()-1; j++) { if(al.get(j+1) > al.get(j)) { flag = 0; continue; } else { flag = 1; break; } } if(flag == 0) { return true; } al.add(i,save); } if(flag == 1) return false; return true; }該代碼用于解決問(wèn)題“給定整數(shù)序列作為數(shù)組，確定是否可以通過(guò)從數(shù)組中刪除不超過(guò)一個(gè)元素來(lái)獲得嚴(yán)格遞增的序列?！睂?duì)于某些測(cè)試用例，它顯示執(zhí)行此操作需要 3 秒以上。但是，我不確定在哪里可以進(jìn)行更改以更快地執(zhí)行它。我無(wú)權(quán)訪問(wèn)測(cè)試用例。在這里，我創(chuàng)建了 2 個(gè) for 循環(huán)，因?yàn)樵诘谝粋€(gè)循環(huán)中，我正在生成將刪除每個(gè)索引的列表，在第二個(gè)循環(huán)中，我正在迭代已刪除元素的新列表。像示例數(shù)組是 {1,2,4,3} 然后在第一個(gè)循環(huán)中我創(chuàng)建一個(gè)數(shù)組，它將是 {2,4,3},{1,4,3},{1,2,3}和{1,2,4}。在第二個(gè)循環(huán)中，我遍歷所有這 4 個(gè)數(shù)組以比較每個(gè)元素。
3 回答
元芳怎么了
TA貢獻(xiàn)1798條經(jīng)驗(yàn) 獲得超7個(gè)贊
主要觀察結(jié)果是列表可以分解為 3 個(gè)（可能為空）部分：
list = list[0..s) + list[s..e) + list[e..length)
Wherelist[0..s)和list[e..length)是嚴(yán)格增加的列表，并且list[s..e)是介于兩者之間的東西。
因?yàn)槟肋@些前綴和后綴列表是嚴(yán)格遞增的，所以您不需要在這些列表中重復(fù)檢查此屬性。
您可以為約束選擇任何值s，但假設(shè)您選擇的值盡可能大，并且盡可能小。e0 <= s <= e < lengthse
如果列表具有所需的整體屬性，則：
s == length，因此列表已經(jīng)嚴(yán)格增加而沒(méi)有刪除任何內(nèi)容。list[s..e)長(zhǎng)度最多為 1 (e-s == 1)，并且list[0..s) + list[e..length)嚴(yán)格遞增。您可以通過(guò)簡(jiǎn)單的比較來(lái)檢查這一點(diǎn)list[s-1] < list[e]。list[s..e)為空 (s == e)，因此您要求list[0..s-1) + list [e..length)（即刪除前綴的最后一個(gè)元素）或list[0..s) + list[e+1..length)（即刪除后綴的第一個(gè)元素）嚴(yán)格遞增。檢查(s == 0 || list[s-1] < list[e])和(e+1 == length || list[s] < list[e+1])分別。如果
list[s..e)有超過(guò) 1 個(gè)元素 (e-s > 1)，則需要?jiǎng)h除多個(gè)元素才能為列表提供所需的屬性。
查找s和e：
s從零處的整數(shù)指針開(kāi)始。遞增它直到它到達(dá)末尾，或者它指向list[0..s)一個(gè)嚴(yán)格遞增列表的元素，但list[0..s+1)不會(huì)。
e從列表長(zhǎng)度的整數(shù)指針開(kāi)始。減少它，而e>s不會(huì)list[e-1..length)是一個(gè)嚴(yán)格增加的列表。
鳳凰求蠱
TA貢獻(xiàn)1825條經(jīng)驗(yàn) 獲得超4個(gè)贊
更新 2：也嘗試此代碼（最多 2 個(gè)循環(huán)） 進(jìn)一步優(yōu)化是可能的，但仍會(huì)產(chǎn)生 O(n) 時(shí)間
public class TstList {
public static boolean compute(int a[]) {
if (compute_1(a))
return true;
return compute_2(a);
}
public static boolean compute_1(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
if (i == 1)
previous = a[i];
else
previous = a[i - 1];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static boolean compute_2(int a[]) {
if (a.length < 2)
return true;
int previous = a[0];
int counter = 0;
for (int i = 1; i < a.length; i++) {
if (previous < a[i]) {
previous = a[i];
continue;
} else {
previous = a[i];
counter++;
}
if (counter > 1)
return false;
}
return true;
}
public static void main(String arg[]) {
System.out.println(compute(new int[] { 1, 2, 3, 4, 6 })); \\1
System.out.println(compute(new int[] { 1, 2, 3, 1, 4, 6 })); \\2
System.out.println(compute(new int[] { 1, 2, 1, 3, 1, 4, 6 })); \\3
System.out.println(compute(new int[] { 1, 2, 3, 4, 6, 3 })); \\4
System.out.println(compute(new int[] { 3, 2, 1 })); \\5
System.out.println(compute(new int[] { 10, 1, 2, 3, 4, 5 })); \\6
System.out.println(compute(new int[] { 1, 2, 5, 3, 5 })); \\7
}
}
輸出
true \\1
true \\2
false \\3
true \\4
false \\5
true \\6
true \\7
嗶嗶one
TA貢獻(xiàn)1854條經(jīng)驗(yàn) 獲得超8個(gè)贊
我會(huì)選擇這個(gè)。
編輯：提供更新的解決方案。它很快，但可讀性不好。我還包含了一個(gè) main() 類(lèi)，其中包含我測(cè)試此代碼的一些標(biāo)準(zhǔn)序列。（以測(cè)試人員很容易驗(yàn)證這一點(diǎn)的格式添加任何額外的案例）。
/**
* Returns true if by removing maximum 1-entry the sequence can be strictly increasing.If not, it returns false. Doesn't check
* if sequence is empty
*/
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
int maxValue = sequence[0];
for (int i = 1; i < length; i++)
{
if (sequence[i] <= maxValue)
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
maxValue = sequence[i];
}
// else { // [i] is a local pit. Remove [i]. maxValue is not updated. }
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
else
{
maxValue = sequence[i];
}
}
return true;
}
public static void main(final String[] args)
{
final List<int[]> testInputs = new ArrayList<>();
final List<Boolean> correctResults = new ArrayList<>();
final List<Boolean> results = new ArrayList<>();
testInputs.add(new int[] { 0 }); // single-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0 }); // two-element sequence
correctResults.add(true);
testInputs.add(new int[] { 0, 0, 0 }); // constant sequence
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 4, 6 }); // strictly increasing
correctResults.add(true);
testInputs.add(new int[] { 3, 2, 1 }); // strictly decreasing
correctResults.add(false);
testInputs.add(new int[] { 10, 1, 2, 3 }); // first value (10) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 1 }); // last value (1) should be removed
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 5, 3, 5 }); // peak (5) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 1, 2, 3, 10, 4, 4, 5 }); // peak (10) followed by constant (4)
correctResults.add(false);
testInputs.add(new int[] { 1, 2, 3, 1, 4, 6 }); // pit (1) (inner value should be removed)
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 2, 6, 7 }); // pit (2) that does not recover
correctResults.add(false);
testInputs.add(new int[] { 5, 0, 3 }); // first value should be removed
correctResults.add(true);
testInputs.add(new int[] { 5, 6, 1, 2 }); // sequence downward gap (pit)
correctResults.add(false);
for (int i = 0; i < testInputs.size(); i++)
{
results.add(checkIfRemovingMaxOneElementItIsStrictlyIncreasing_NoAssignment(testInputs.get(i)));
if (correctResults.get(i) == results.get(i))
{
System.out.println("Test case: " + i + " successful.");
}
else
{
System.out.println("Test case: " + i + " should be: " + correctResults.get(i) + " but was: " + results.get(i));
System.out.println("Test case: " + i + " input array: " + Arrays.toString(testInputs.get(i)));
}
}
}
此外，如果您不關(guān)心特定值是否被破壞，則可以避免使用額外的變量：
private static boolean checkIfRemovingMaxOneElementItIsStrictlyIncreasing_WithoutAssignment(final int[] sequence)
{
boolean isFirstNonDecreasingSequence = true;
final int length = sequence.length;
for (int i = 1; i < length; i++)
{
if (sequence[i] <= sequence[i - 1])
{
if (isFirstNonDecreasingSequence == true)
{
if ((i + 1) < length) // check this is not the last element
{
if ((sequence[i - 1] >= sequence[i + 1])) // Check if it is peak or pit
{
// [i-1] is a local peak. Remove [i-1]
if (i > 1)
{
// Check if by removing [i-1] the sequence is actually increasing
if (sequence[i] <= sequence[i - 2])
{
return false;
}
}
}
else
{
// [i] is a local pit. Remove [i]
sequence[i] = sequence[i - 1];
}
isFirstNonDecreasingSequence = false;
}
}
else
{
return false;
}
}
}
return true;
}
在這兩個(gè)版本中，代碼中都有很多 if。這是真的，但它們只會(huì)在序列第一次檢測(cè)到兩個(gè)連續(xù)值的非遞增序列時(shí)執(zhí)行。所以在性能方面這應(yīng)該沒(méi)問(wèn)題。
至于邏輯：
當(dāng)它在索引[i]處檢測(cè)到：A[i-1]>=A[i]時(shí)，它確定它是否在一個(gè)峰值之后（因此A[i-1]是“異?！备卟⑶覒?yīng)該從序列中刪除）或者它在一個(gè)坑內(nèi)（A[i] 太低，應(yīng)該從序列中刪除）。
添加回答
舉報(bào)
0/150
提交
取消