Problem:
(This is a slightly harder version of the fix34 problem.) Return an array that contains exactly the same numbers as the given array, but rearranged so that every 4 is immediately followed by a 5. Do not move the 4's, but every other number may move. The array contains the same number of 4's and 5's, and every 4 has a number after it that is not a 4. In this version, 5's may appear anywhere in the original array.
fix45({5, 4, 9, 4, 9, 5}) → {9, 4, 5, 4, 5, 9}
fix45({1, 4, 1, 5}) → {1, 4, 5, 1}
fix45({1, 4, 1, 5, 5, 4, 1}) → {1, 4, 5, 1, 1, 4, 5}
Solution:
public int[] fix45(int[] nums) {
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 4) {
for (int j = 0; j < nums.length; j++) {
if (nums[j] == 5) {
if (j > 0 && nums[j-1] != 4) {
int tmp = nums[i+1];
nums[i+1] = 5;
nums[j] = tmp;
}
else if (j == 0) {
int tmp = nums[i+1];
nums[i+1] = 5;
nums[j] = tmp;
}
}
}
}
}
return nums;
}
Better optimized code with complexity less than n^2. need not search the entire array again and again for 5. just break when you find the first 5 . when looping again start from the point where you found the first 5.
ReplyDeletepublic int[] fix45(int[] nums) {
int index=0;
for(int i=0;i<=nums.length-2;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=index;j<=nums.length-1;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
index++;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
index=j;
break;
}
}
}
}
return nums;
}
Better optimized code with complexity less than n^2. need not search the entire array again and again for 5. just break when you find the first 5 . when looping again start from the point where you found the first 5.
ReplyDeletepublic int[] fix45(int[] nums) {
int index=0;
for(int i=0;i<=nums.length-2;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=index;j<=nums.length-1;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
index++;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
index=j;
break;
}
}
}
}
return nums;
}
Hey:) Here's a clearer version, you don't need index at all. This is your solution - all credit goes to you:
Deletepublic int[] fix45(int[] nums) {
for(int i=0;i<nums.length-1;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=0;j<nums.length;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
break;
}
}
}
}
return nums;
}
Here is even more clear(don't need break)
Deletepublic int[] fix45(int[] nums) {
for(int i=0;i<nums.length-1;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=0;j<nums.length;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
}
}
}
}
return nums;
}
Here is even more clear(don't need break)
Deletepublic int[] fix45(int[] nums) {
for(int i=0;i<nums.length-1;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=0;j<nums.length;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
}
}
}
}
return nums;
}
Hey:) Here's a clearer version, you don't need index at all. This is your solution - all credit goes to you:
Deletepublic int[] fix45(int[] nums) {
for(int i=0;i<nums.length-1;i++){
if(nums[i]==4 &&nums[i+1]!=5){
for(int j=0;j<nums.length;j++){
if(nums[j]==5 && j==0){
nums[0]=nums[i+1];
nums[i+1]=5;
}
if(nums[j]==5 && nums[j-1]!=4){
nums[j]=nums[i+1];
nums[i+1]=5;
break;
}
}
}
}
return nums;
}
This is what I came up with:
ReplyDeletepublic int[] fix45(int[] nums) {
int len = nums.length;
int temp;
for (int i = 0; i < len - 1; i++) {
if (nums[i] == 4 && nums[i + 1] != 5) {
for (int j = len - 1; j >= 0; j--) {
if (nums[j] == 5) {
if (j - 1 >= 0 && nums[j - 1] != 4 || j == 0) {
temp = nums[i + 1];
nums[i + 1] = nums[j];
nums[j] = temp;
}
}
}
}
}
return nums;
}
Can't say that it's better than what was already suggested, but here you go anyway.
ReplyDeletepublic int[] fix45(int[] nums) {
int temp = 0;
for (int i=0; i0 && nums[x]==5 && nums[x-1]!=4))
{
nums[x]=nums[i+1];
nums[i+1]=5;
break;
}
}
}
return nums;
}
public int[] fix45(int[] nums) {
ReplyDeleteint pos5 = 0; // will hold the position of the next 5
for (int i=0 ; i0 && nums[pos5-1]==4) // search for the next 5
pos5++;
nums[pos5++]=nums[++i];
nums[i]=5;
}
return nums;
}
public int[] fix45(int[] nums) {
Deleteint pos5 = 0; // will hold the position of the next 5
for (int i=0 ; i < nums.length-1 ; ++i)
if (nums[i] == 4 && nums[i+1] != 5){
while (nums[pos5] != 5 || pos5 > 0 && nums[pos5-1] == 4) // search for the next 5
pos5++;
nums[pos5++] = nums[++i];
nums[i] = 5;
}
return nums;
}
Easy and clever technique!!!
ReplyDeletepublic int[] fix45(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length; j++) {
if (nums[i] == 5 && nums[j] == 4) {
int t = 0;
t = nums[j + 1];
nums[j + 1] = nums[i];
nums[i] = t;
}
}
}
return nums;
}
public int[] fix45(int[] nums) {
ReplyDelete//Fast Solution//
int pos = 0;
boolean found = false;
for (int i = 0; i < nums.length - 1; i++)
{
if (nums[i] == 4)
{
for (int j = pos; j < nums.length && !found; j++)
{
if (nums[j] == 5 && (j == 0 || nums[j - 1] != 4))
{
nums[j] = nums[i + 1];
nums[i + 1] = 5;
found = true;
pos = j;
}
}
}
found = false;
}
return nums;
}
public int[] fix45(int[] nums) {
ReplyDeleteint l=nums.length;
int[] ar=new int[l];
for (int i=0; i<l ; i++){
if (nums[i]==4) {
ar[i]=4;
ar[i+1]=5;
}
}
for (int i=0; i<l ; i++){
if (nums[i]!=4 && nums[i]!=5){
for (int j=0; j<l ; j++){
if (ar[j]!=4 && ar[j]!=5) ar[j]=nums[i];
}
}
}
return ar;
}